图的遍历：DFS、BFS 与连通分量

学完图的基本概念和存储方式之后，第一件真正要做的事，通常就是遍历。因为一张图只靠“画出来”是没有意义的，真正要解决问题时，你总要从某个顶点出发，沿着边把可达区域探索出来。图的遍历，正是在回答这样一个问题：

如何系统地访问图中的顶点，使得每个相关顶点都被按某种规则走到？

和树遍历相比，图遍历更复杂。因为图可能：

有环；
不连通；
存在多条不同路径；
在有向图中还可能出现单向可达。

这就意味着，图遍历不能像树那样只靠递归定义自然展开，还必须考虑“是否访问过”的状态管理。也正因为此，DFS 和 BFS 不只是两种遍历方式，它们几乎是整个图算法体系的起点。很多图问题表面不同，本质上都离不开这两种搜索框架。

一、为什么图遍历比树遍历更复杂

树里最好的性质之一是：

通常没有环；
从根出发不会绕回来；
父子关系比较明确。

但图中情况完全不同：

走过的点可能再次通过别的边走回来；
一条边可能把你带回之前访问过的区域；
甚至整张图可能由多个互不连通部分组成。

所以图遍历的第一原则就是：

必须记录哪些顶点已经访问过，防止无限重复。

这也是 visited 标记在图遍历里如此关键的原因。

二、什么是深度优先搜索 DFS

DFS，英文是 Depth First Search，可以理解成：

从当前顶点出发，优先沿着一条路径一直走到尽头，走不动了再回退，继续探索其他分支。

这和前面树里的递归遍历有很强的亲缘关系。它的味道通常是：

先尽可能深入；
再逐层回溯；
本质上是一种“路径优先”的搜索方式。

三、DFS 为什么和栈紧密相关

因为 DFS 的核心行为就是：

沿着当前路径不断深入；
走不通时回到最近的分叉点；
再尝试新的分支。

这里“最近分叉点优先回退”本质上就是后进先出，因此：

递归版 DFS 依赖系统调用栈；
非递归版 DFS 通常显式使用栈。

所以你可以把 DFS 看成“栈思想在图上的应用”。

四、什么是广度优先搜索 BFS

BFS，英文是 Breadth First Search，可以理解成：

从起点出发，先访问所有距离为 1 的顶点，再访问距离为 2 的顶点，然后是距离为 3 的顶点，按层次一圈圈向外扩展。

它和 DFS 完全不同，不强调先走深，而强调“先近后远”。

所以 BFS 的典型特征是：

很像波纹向外扩散；
更关注层次和最短步数；
本质上是一种“按层推进”的搜索。

五、BFS 为什么和队列紧密相关

因为 BFS 的访问规律是：

先发现的顶点，应该先展开它的邻居；
后发现的顶点排在后面等待。

这正是先进先出的过程。所以 BFS 几乎天然和队列绑定：

起点先入队；
每次出队一个顶点并访问；
再把它尚未访问过的邻居入队；
重复直到队列为空。

所以也可以说，BFS 是“队列思想在图上的应用”。

六、DFS 和 BFS 最核心的差异是什么

可以先抓住一句最本质的话：

DFS 优先把一条路走深，BFS 优先把同一层走完。

于是它们的适用味道也会很不同。

1. DFS 更适合

看路径结构；
做回溯；
找连通块；
判断是否存在某种深层结构；
做拓扑、强连通等更深层图分析的基础。

2. BFS 更适合

求无权图最短路；
按层推进；
最近层、最少步数问题；
波次扩散类问题。

七、图遍历为什么通常要外层再套一层循环

因为图可能不连通。

如果你只从某一个起点做 DFS 或 BFS，那么你只能访问到和它同一个连通块里的顶点。那些和它完全不相连的部分，根本不会被走到。

所以如果题目目标是“遍历整张图”或“统计图中有多少个连通分量”，典型做法通常是：

枚举所有顶点；
遇到还没访问过的顶点，就从它重新启动一次 DFS / BFS；
每启动一次，通常就意味着发现了一个新的连通分量。

这一步非常关键。

八、什么是连通分量

在无向图中，连通分量可以理解成：

图中一个极大连通子图，其中任意两个顶点彼此可达。

换句话说：

同一分量里的点能互相到达；
不同分量之间没有路径相通。

所以统计连通分量，本质上就是：

看整张图被分成了多少块互相独立的区域。

而 DFS / BFS 恰好非常适合做这件事。

九、DFS / BFS 如何求连通分量

基本思路都一样：

先把所有顶点标记为未访问；
从第一个未访问顶点开始做一次搜索；
这一轮能访问到的所有顶点，属于同一个连通分量；
再继续找下一个未访问顶点，开启下一轮搜索；
重复直到全部访问完。

于是：

搜索启动次数 = 连通分量个数。

这说明连通分量并不是额外的新算法，而是 DFS / BFS 的一个非常直接的应用。

十、BFS 为什么能求无权图最短路

这是 BFS 最经典的应用之一。

在无权图里，每条边代价都相同，可以看成一步。BFS 从起点出发时：

第一层是距离 1 的点；
第二层是距离 2 的点；
第三层是距离 3 的点。

因为它按层推进，所以第一次到达某个顶点时，走到它的边数一定是最少的。

也就是说：

BFS 的层数，本身就是无权图中的最短步数。

这也是为什么很多“最少操作次数”“最短变换步数”类问题，第一反应常常应该是 BFS。

十一、DFS 更适合哪些“结构性问题”

DFS 的强项往往不是最短路，而是更偏结构探索和递归分析。

例如：

判断图中是否有环；
找所有可达点；
枚举路径；
做回溯搜索；
后面做拓扑排序、强连通分量等。

因为 DFS 能天然保留“当前路径”的语境，所以对很多需要递归展开和回退的问题特别合适。

十二、图遍历的复杂度怎么理解

如果图用邻接表表示，那么 DFS 和 BFS 的典型复杂度通常是：

1	O(\|V\| + \|E\|)

原因是：

每个顶点通常只会入栈 / 入队 / 访问一次；
每条边也只会被检查有限次。

如果用邻接矩阵表示，由于遍历某个顶点邻居需要扫整行，复杂度通常更接近 O(|V|^2)。

这也再次说明：图算法的效率和存储方式关系非常紧密。

十三、学习图遍历时最容易踩的坑

1. 忘记 visited 标记

这是最常见、也最致命的问题，尤其在有环图中会直接导致死循环。

2. 只会从一个起点遍历，不考虑图不连通

这会漏掉整张图中的其他分量。

3. 把 DFS 和 BFS 用反

例如本来是最短步数问题，却上来就写 DFS，结果又慢又绕。

4. 不结合存储方式分析复杂度

邻接矩阵和邻接表下，遍历成本差别会很明显。

总结

图的遍历之所以重要，不只是因为它是图论入门，而是因为很多图问题本质上都只是 DFS / BFS 的不同变体。真正值得先建立起来的，是这些核心认识：

图遍历比树遍历更复杂，因为图可能有环、可能不连通；
DFS 强调先深入再回退，本质上依赖栈；
BFS 强调按层推进，本质上依赖队列；
BFS 很适合无权图最短步数问题，DFS 更适合结构探索和回溯；
连通分量统计本质上就是多次启动 DFS / BFS；
真正学会图遍历，不是只会写两段模板，而是能根据题目味道判断应该“先走深”还是“先走广”。

把这一篇理解透之后，后面再去学拓扑排序、最短路径、最小生成树时，你会更自然地把它们看成是在 DFS / BFS 基础上叠加约束和优化，而不是完全陌生的新东西。

参考资源：