连通分量与环
复习
- 图的表示：邻接矩阵与邻接表
- 广度优先搜索：一层一层向外扩张
- 深度优先搜索：沿一条路走到底
TL;DR
- 连通分量是图中互不相连的若干部分
- 从每个未访问节点搜一遍，就能数出连通分量
- 有向图判断连通更强，要区分方向
- 检测环对依赖分析非常重要
正文
有了 BFS 和 DFS，就可以回答关于图的两个基本问题了：这张图分成几块？有没有环？
分成几块：连通分量
在无向图里，如果两个节点之间存在路径，它们就是连通的。整张图可能分成好几个互不相连的部分，每一部分叫一个连通分量（connected component）。
怎么找出它们？用前面学的遍历就行：
- 从某个没访问过的节点出发，做一次 BFS 或 DFS，它会把和它连通的所有节点都访问到
- 这些节点，就构成一个连通分量
- 再找下一个还没访问的节点，重复，直到所有节点都被访问
能做几次完整的遍历，就说明有几个连通分量。 一个看似复杂的问题，用“标记已访问 + 遍历”就解决了。
在有向图里，事情更微妙，因为方向会破坏对称性：A→B 不代表能 B→A。于是有“强连通”的说法——两个节点能互相到达才算强连通。整个有向图可以被拆成若干强连通分量，这在分析依赖、循环时很有用。
有没有绕回来：找环
检测环，对很多问题至关重要。比如一堆任务互相依赖，如果形成一个圈（A 等 B、B 等 C、C 等 A），那就永远无法开始——这正是死锁的雏形。
找环的思路，也是基于遍历：
- 无向图：DFS 时若遇到一个“已访问的、且不是当前节点父节点”的邻居，说明绕回来了，存在环
- 有向图：DFS 时若遇到一个“还在当前递归路径上”的节点（也就是指向祖先的回边），就说明有环
核心直觉都是：沿着一条路深入时，如果撞见了自己来时的路上某个节点，那就绕回原点了。
有了“判断是否有环”的能力，我们就可以处理那类“有前后依赖”的任务了。下一章，拓扑排序。
思考题 1
怎样用一次图遍历，找出所有的连通分量？
思考题 2
为什么“检测环”对依赖关系特别重要？
小结
知识点
- 连通分量是图中互不相连的部分
- 对每个未访问节点做一次遍历即可统计
- 有向图需用强连通的概念
- 找环基于遍历，无向图与有向图判法不同
参考资料
- Wikipedia(zh)：连通分量：图中互相连通的部分
- Wikipedia(zh)：环 (图论)：首尾相连的路径
思考题答案（仅供参考）
思考题 1
从任意一个未访问的节点出发做一次 BFS 或 DFS，把能到达的节点都标记为已访问，这些节点构成一个连通分量；再找下一个未访问的节点重复，直到所有节点访问完毕。遍历的次数就是连通分量的个数。
思考题 2
因为依赖关系一旦成环，就意味着任务互相等待，谁也无法开始，比如循环依赖、死锁。能检测出环，就能提前发现这种“永远无法完成”的问题，避免系统卡死。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪