图的遍历与连通性

图的遍历不仅是“访问所有顶点”的算法模板，也能反映图的连通性。复习时先分清图的类型：无向图看连通分量，有向图看沿弧方向的可达范围；强连通图才有“任一顶点出发都能覆盖全部”的性质。

相关卡片：图的定义、无向图与有向图、广度优先搜索、深度优先搜索、图的连通性与连通分量、Tarjan 算法、图的关系概念速查表。

图的遍历与连通性

无向图：调用次数就是连通分量数

对无向图执行完整遍历时，常见框架是：

1
2
3
4
5
for (int i = 0; i < vertexCount; ++i) {
    if (!visited[i]) {
        Search(G, i, visited);  // Search 可以是 BFS 或 DFS
    }
}

这里的关键是：每次从一个未访问顶点启动 BFS/DFS，都会完整覆盖该顶点所在的连通分量。由于不同连通分量之间没有路径，前一次遍历不可能跨到另一个分量。

因此对无向图：

图的情况 BFS/DFS 调用次数 结论
连通图 $1$ 从任一顶点出发都能访问全部顶点
非连通图，有 $k$ 个连通分量 $k$ 每个连通分量需要启动一次遍历

这也是判断无向图连通性的常用方法：任选一个顶点做一次 BFS/DFS，若能访问所有顶点，则图连通；否则不连通。

有向图：调用次数要具体分析

有向图的边有方向，遍历只能沿弧方向走。即使把方向忽略后看起来“连在一起”，也不代表从某个起点沿出边能访问全部顶点。

对有向图执行 BFS/DFS 时：

  • 若起始顶点到其他所有顶点都有路径，则从这个起点只需调用一次 BFS/DFS。
  • 若起始顶点不能到达所有顶点，完整遍历还需要外层循环从未访问顶点继续启动。
  • 调用次数取决于顶点扫描顺序和各顶点的可达范围，不能简单等同于强连通分量数。
  • 若有向图是强连通图，则从任一顶点出发都只需调用一次 BFS/DFS。
有向图不要套无向图结论

无向图中“调用次数 = 连通分量数”很稳定；有向图中，普通 BFS/DFS 的调用次数要看出发顶点能沿弧方向到达哪些顶点。若要系统讨论有向图内部互相可达的极大区域，应使用强连通分量，实际算法可看 Tarjan 算法。

## BFS 与 DFS 在连通性问题中的用法
任务 BFS DFS 选择建议
判断无向图是否连通 从任一顶点出发，看是否访问全部顶点 同样可做 两者都可
统计无向图连通分量数 外层循环多次启动 BFS 外层循环多次启动 DFS 调用次数即分量数
生成森林 得到广度优先生成森林 得到深度优先生成森林 看题目要求层次还是深入路径
判断有向图从某起点是否可达全部顶点 可做 可做 只需看一次遍历后的 visited[]
判断有向图是否强连通 需要进一步检查反向可达或使用 SCC 算法 需要进一步检查反向可达或使用 SCC 算法 不要只做一次普通遍历
判断有向图是否有环 不常用普通 BFS 直接判 使用三色 DFS 很自然 见 DFS 判有向图环

遍历序列、生成树与存储结构

遍历序列和生成树都不只由图本身决定，还受起点和邻接点访问顺序影响。

  • 起点不同，BFS/DFS 序列通常不同。
  • 邻接矩阵在顶点编号固定时表示唯一，邻接点扫描顺序通常固定，因此序列和生成树通常唯一。
  • 邻接表表示方式不唯一，同一顶点的邻接点链表顺序可变，因此序列和生成树可能不唯一。
  • BFS 记录第一次发现顶点的边，形成广度优先生成树或森林。
  • DFS 记录第一次递归进入顶点的边，形成深度优先生成树或森林。

考试速记

  • 无向图完整 BFS/DFS：调用次数 = 连通分量数。
  • 无向连通图：从任一顶点出发，只需一次 BFS/DFS。
  • 有向图普通 BFS/DFS：调用次数具体分析，取决于沿弧方向的可达范围。
  • 有向强连通图：从任一顶点出发，只需一次 BFS/DFS。
  • 判断无向图连通性：一次遍历后看 visited[] 是否全为 true。
  • 判断有向图强连通性：不能只靠一次普通遍历；要检查双向可达或求强连通分量。