说起图的 BFS 遍历和 DFS 遍历很多学数据结构的人第一反应是“不就是树的层序和先序换到图上嘛”。可真动手写 C 代码时就会发现树里那个天然的父子关系帮你挡住了很多细节图里没有你得自己处理“怎么保证不重复访问”“一个点可能连接所有点”“非连通图怎么办”这一连串问题。这篇就是基于我平时写图的实战经验把 BFS 遍历和 DFS 遍历完整走一遍从存储结构选型到最终代码每一步都解释为什么这么做。适合正在啃数据结构图这一章的同学也适合面试前想快速拾起手写遍历代码的人。1. 图的存储结构选型邻接矩阵还是邻接表1.1 邻接矩阵用二维数组直接表达两点关系图的存储选择会直接影响 BFS 和 DFS 代码的写法所以先把这个基础定下来。邻接矩阵是个二维数组matrix[u][v]表示顶点 u 到顶点 v 是否有边。无权图用 0/1有权图直接存权重没有边就填一个很大的数表示不可达。用邻接矩阵的最大好处是判断两个点是否直接相邻非常快O(1) 时间直接matrix[u][v]查一下就行。代码写起来也直观初始化一个vectorvectorint matrix(n, vectorint(n, 0))读边时给对应位置赋值。对于无向图别忘了一句话无向图的矩阵是对称的matrix[u][v]和matrix[v][u]都要更新否则后面遍历会漏边。但它的问题也很突出。假设图里有一万个顶点却只有两万条边这时邻接矩阵依然要开一亿个整数的空间。我见过不少同学用邻接矩阵做大数据量的题目还没开始遍历内存先超限了。而且遍历某个顶点的所有邻居时你还得把整行扫一遍明明只有一个邻居也要循环一万次时间复杂度被无脑拉高。所以邻接矩阵更适合稠密图或者顶点数量很少、但边非常多的情况。1.2 邻接表把“每个顶点连了谁”这件事单独存下来邻接表的思路更贴近图的本质不为不存在的边浪费空间。它的做法是给每个顶点维护一个列表列表里放的是从这个顶点能直接到达的邻居。C 里最常用的载体就是vectorvectorint adj(n)读入一条 u 到 v 的边时执行adj[u].push_back(v)如果是无向图再执行一次adj[v].push_back(u)。这种方式在遍历时非常舒服。想拿某个点的全部邻居直接for (int v : adj[u])就可以循环次数和这个点的度成正比而不是和总顶点数成正比。整个图的空间复杂度是 O(VE)对稀疏图特别友好。实际刷题、工程实现、面试手写绝大多数场景下我都推荐邻接表它读边、遍历、统计邻居的操作都足够自然。如果图带权重邻接表也不是只能存整数。可以把adj定义成vectorvectorpairint,intpair 里第一个值是邻居编号第二个值是边权或者定义一个struct Edge { int to, weight; }。这样后续写 Dijkstra、Prim 这类算法时邻接表可以直接复用不用推倒重来。1.3 两种存法怎么选看图的长相就能定选存储结构时我一般先判断一个比例边的数量相对于顶点数量是接近 O(V^2) 还是接近 O(V)。如果边多到几乎任意两个顶点之间都可能有边用邻接矩阵判断两点相连的速度优势能发挥出来如果边明显稀疏无脑邻接表。两者在 BFS 和 DFS 上的复杂度差异也要心里有数。邻接表遍历时每条边被访问一次每个顶点被入队或入栈一次整体 O(VE)邻接矩阵遍历时处理每个顶点都要扫描整行整体 O(V^2)。同一个算法换个存储结构复杂度可能就从能跑变成不能跑这是我在实际题目里踩过坑之后才深刻体会的。存储结构空间复杂度判断 u、v 是否相邻遍历 u 的所有邻居适用场景邻接矩阵O(V^2)O(1)O(V)稠密图、顶点数小邻接表O(VE)需要遍历邻居列表O(degree(u))稀疏图、大多数场景2. BFS 遍历为何用队列从零开始写出代码2.1 BFS 的核心理念水波纹一样一层层扩散BFS 的英文是 Breadth First Search广度优先搜索。它的遍历顺序可以用一个特别生活化的例子理解你往平静的水面扔一颗石子波纹先向外扩散一圈再扩散第二圈、第三圈。BFS 就是从起始顶点出发先把距离为 1 的所有邻居访问完再访问距离为 2 的所有邻居依次类推。要实现这种“先来的先处理”的顺序队列是天然匹配的数据结构。队列是先进先出你从起点开始把起点放进队列然后将它的所有邻居放进队列。因为队列先处理的是起点所以起点的邻居们会排在后面但起点的所有邻居之间又是按放入队列的先后顺序被处理的。这样整个访问顺序就严格按距离分层推进不会出现一个深层的点半路插队的情况。BFS 能求出无权图最短路径靠的就是这个分层特性。我第一次真正理解这一点时忽然觉得图也没那么抽象从起点出发第一次到达某个顶点时经历的边数一定是从起点到该顶点的最短路径长度。所以只要在遍历时记录下每个点被访问时所在的层数最短距离自然就出来了。2.2 BFS 的 C 实现邻接表版完整代码下面这段代码是 BFS 最典型的写法。我加了一些注释方便你直接对照思路。#include iostream #include vector #include queue using namespace std; void bfs(int start, const vectorvectorint adj) { int n (int)adj.size(); vectorchar visited(n, 0); // 用 char 当 bool 数组省一点内存 queueint q; visited[start] 1; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); cout visit u endl; for (int v : adj[u]) { if (!visited[v]) { visited[v] 1; q.push(v); } } } }这段代码里有一个关键细节你是在把顶点v放入队列的那一刻就标记visited[v] 1而不是等它从队列里弹出时再标记。这个顺序非常重要我在后面第四章会专门展开说。如果等到弹出时才标记同一个顶点可能被多个邻居反复放进队列队列里会出现大量重复元素严重时直接内存飙升甚至死循环。要记录从起点到每个点的最短距离只需要把visited换成dist数组初始值设成 -1 表示未访问。vectorint bfsDist(int start, const vectorvectorint adj) { int n (int)adj.size(); vectorint dist(n, -1); queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return dist; }dist[u] 1这一段是精髓u 是第一层到达的那它的邻居 v 自然就是下一层距离加一。因为 BFS 是按层扩散的这个 1 永远不会被更大的值覆盖你最终得到的就是最短步数。2.3 BFS 不只用于遍历这几个场景直接能用BFS 的价值远不只是打印访问顺序。最常见的应用是迷宫最短步数问题把每个格子看成顶点上下左右能走到的格子看成边从入口 BFS 到出口首次弹出的终点距离就是最短步数。这是最典型的“图上的最短路”模型前提是每一步的代价都相等。另一个常见场景是多源 BFS。比如地图上有多个着火点火烧到每个格子的最短时间就可以把所有着火点当成起点同时放入队列然后一起 BFS。这类似于从多个石子同时扔进水面波纹各自向外扩散谁先碰到某个格子谁就决定了这个格子被影响的时刻。多源 BFS 的代码实现只比单源多了一步初始化时把所有源点都 push 进队列并标记 visited。还有一个很适合 BFS 的应用是判断二分图。从一个顶点开始把它染成颜色 1它的所有邻居染成颜色 2邻居的邻居再染回颜色 1。如果 BFS 过程中发现某个顶点的邻居已经被染成了和它一样的颜色那这张图就不是二分图。这个思路用 DFS 也能做但 BFS 的按层扩展更符合“逐层染色”的直觉。3. DFS 遍历一条路走到黑再回头换条路3.1 DFS 的核心理念递归和栈是天然搭档DFS 的英文是 Depth First Search深度优先搜索。它的性格和 BFS 完全相反从起点出发沿着一条边一直往下走走到没有未访问的邻居了才返回上一层再尝试另一条边。这个过程很像你在一个陌生迷宫里探险碰到岔路就选一条走到底走不通了回到上一个岔路口换一条。树的先序遍历其实就是一种 DFS只不过树的每个节点最多只有两个子节点方向很明确。图不一样一个顶点可能有十几个邻居DFS 的“回头”机制就更重要了。实现 DFS 最常见也最好写的方式是递归因为递归函数本身就自带调用栈你进入一个函数就相当于深入一层函数返回就相当于回溯到上一层。如果你不想用递归也可以用显式的栈来模拟这个过程。每探访一个顶点就把它的未访问邻居压入栈然后总是从栈顶取顶点继续深入。这和 BFS 只差一个数据结构BFS 用队列DFS 用栈。理解了这一点两种遍历方式的本质基本就打通了。3.2 DFS 的 C 实现递归版与显式栈版递归版 DFS 是最容易写错的版本但只要记住一件事进入函数时立刻标记 visited。下面是完整实现。#include iostream #include vector using namespace std; void dfs(int u, const vectorvectorint adj, vectorchar visited) { visited[u] 1; cout visit u endl; for (int v : adj[u]) { if (!visited[v]) { dfs(v, adj, visited); } } }你可能会奇怪为什么递归里没有“回溯恢复 visited”的步骤。因为这里是遍历整张图一个顶点一旦被访问过后面就没必要再访问了如果每条路径都要恢复 visited那复杂度会爆炸变成指数级那是在求“所有路径”而不是在“遍历图”。很多同学混淆了遍历和回溯法一上来就在 DFS 里重置 visited结果同一张图被反复访问无数次运行时间暴涨。如果图特别大递归深度可能达到几十万层程序会栈溢出。这时候显式栈就派上用场了。#include iostream #include vector #include stack using namespace std; void dfsIter(int start, const vectorvectorint adj) { int n (int)adj.size(); vectorchar visited(n, 0); stackint st; st.push(start); visited[start] 1; while (!st.empty()) { int u st.top(); st.pop(); cout visit u endl; for (int v : adj[u]) { if (!visited[v]) { visited[v] 1; st.push(v); } } } }注意这个显式栈版本里我在入栈时就标记 visited。如果不这样做同一个顶点可能会被多个邻居重复压栈。比如说顶点 x 有两个邻居 a 和 ba 在遍历时发现 x 可以走把 x 压进去b 遍历时又看到 x又压进去一次。栈里就出现两个 x最终虽然结果不一定全错但效率很差处理复杂图时会有大量重复计算。3.3 DFS 的典型应用从找路径到拓扑排序DFS 最常见的应用是检测图中是否存在环。在无向图中如果 DFS 遍历时遇到一个已经访问过但不是“上一个顶点”的邻居说明有环在有向图中更严谨的做法是使用三色标记法白色表示未访问灰色表示正在当前递归栈中黑色表示已经递归完成。如果 DFS 过程中遇到了灰色节点说明存在环。这种技巧在很多依赖关系分析、编译依赖检测的场景里非常实用。DFS 也是生成拓扑排序的经典方式之一。拓扑排序解决的是“有向无环图里先做哪个任务后做哪个任务”的问题。用 DFS 做拓扑排序的步骤很巧妙当一个顶点的所有后继都处理完毕之后再把这个顶点加入结果序列最后把整个结果反转就得到一种合法的拓扑序。我第一次看到这个反转时觉得不太直观但画几个依赖关系图走一遍很快就会理解递归的反向顺序正好是依赖的前置顺序。DFS 还广泛应用于连通分量问题。调用一次 DFS 能访问到的所有顶点就是当前连通分量的全部成员。把每个连通分量分别跑一次 DFS就能统计出一个图里有几个互相不连通的“岛屿”这在社交网络、图像区域识别里都有直接应用。4. 遍历代码中的易错点与排查经验4.1 非连通图别只从一个顶点出发就以为遍历完了这是新手最容易犯的错误。我见过很多人的 BFS 和 DFS 代码是这样写的调用一次bfs(0, adj)看到输出了一些顶点就认为整张图都遍历完了。但如果图本身是不连通的比如 0 和 1 有边2 和 3 有边这两组之间根本没有通路那么从 0 出发的 BFS 只能访问{0, 1}{2, 3}会一直被漏掉。正确的做法是包一层循环遍历图的所有顶点只要某个顶点还没被访问过就把它作为新的起点再调用一次 BFS 或 DFS。这也相当于统计连通分量的数量。void bfsAll(const vectorvectorint adj) { int n (int)adj.size(); vectorchar visited(n, 0); for (int i 0; i n; i) { if (!visited[i]) { bfs(i, adj, visited); // 注意把 visited 传进 bfs避免重复分配 } } }bfs函数需要额外加一个参数vectorchar visited并把原来内部的 visited 声明删掉。这样一来整个外层循环结束后所有连通分量都被访问到了。面试时如果题目没说图一定连通最好主动加上这层保护能避免很多边界情况。4.2 visited 标记的时机早一步省心晚一步崩溃标记 visited 的时机是图遍历里最重要的小细节。先说 BFS当顶点 v 被放入队列时就立刻标记 visited。这样做可以用一个很简单的场景解释假设图是 a - b 双向边也就是邻接表里adj[a]包含 badj[b]包含 a。如果 a 入队出队后遍历到 b把 b 放入队列但不标记随后 b 出队遍历到 a因为 a 没有被标记a 又被放进队列。于是 a、b 会不断互相放入队列形成一个死循环队列大小无限增长。DFS 同理。递归版在进入函数的第一行标记 visited显式栈版在把顶点压栈时标记 visited。核心原则只有一个只要一个顶点已经进入了待访问结构队列或栈它就不再是“未访问”状态。宁可标记得早一些也不要为了输出顺序而推迟标记。在实际排查时如果发现程序“卡死”或内存暴涨第一步就是检查 visited 标记的位置。4.3 递归爆栈图规模一大栈就顶不住递归版 DFS 虽然写起来爽但它有一个硬伤递归深度等于 DFS 实际深入的层数。对于一个链状的图一万个顶点可能递归一万层程序在抵达终点之前就把调用栈耗尽了。我在调试大规模图数据时遇到最多的问题就是 “Segmentation fault” 或者程序毫无征兆地退出排查到最后往往是递归栈不够。解决方式有几种。第一把递归版改成显式栈版这是最通用、最不受平台限制的做法。第二如果一定想用递归可以尝试在编译时调大栈空间但不同系统、不同编译器的参数不一样不推荐在跨平台项目里依赖这个。第三如果只是做题可以估算一下递归深度和总顶点数明显超过十万时直接放弃递归版。显式栈的代码量没有多多少稳定性却高很多。4.4 BFS 需要记录层数时队列里存 pair 还是分轮处理很多 BFS 场景不只想打印访问顺序还想知道每个顶点距离起点有几层。除了用 dist 数组还有两种常见的写法。一种是队列里直接存pairint, int第二个 int 表示层数处理时取出来用。这个方法简单直观适合层数不多的小图缺点是每个队列元素都多存了一个 int空间占用略高。另一种方法是分层处理记录当前这层的元素个数 size循环 size 次处理完这一层层数自增一。这个写法适合需要按层做额外操作的场景比如打印每一层的顶点列表或者统计每一层的节点数。两种方法本质一样选哪种取决于你更关心代码可读性还是内存占用。我个人更常用 pair 版本因为它最不容易写错。5. 从遍历到实战BFS 和 DFS 还能解决什么5.1 BFS 实战最短路、多源扩散、状态搜索前面提到了 BFS 能求无权图最短路径这里再扩展一下。如果你面对的图是网格状迷宫每一步的代价都相同那么 BFS 几乎是最优解。把二维坐标映射成一维顶点编号就能直接套用bfsDist的模板。我在处理这类题目时习惯用方向数组dx[4] {-1, 1, 0, 0}和dy[4] {0, 0, -1, 1}四个方向逐个扩展每扩展一步就检测目标点是否已被访问直到队列为空。多源 BFS 的应用也很广泛比如多个仓库同时向周边发货求最后一个被覆盖到的点需要多久。实现上就是把所有源点都初始化入队dist 全部设为 0然后正常 BFS。这里要提醒一句如果源点之间也有相互可达的关系visited 仍然要在入队时标记否则多源也会出现重复入队问题。BFS 还能做状态空间搜索。八数码、华容道这类问题可以把一个状态看成一个顶点一次移动看成一条边目标就是从初始状态 BFS 到目标状态。这种题目状态总数可能很大但只要状态转移规则允许BFS 就能保证找到最少步数。只是实际写的时候要小心状态去重避免同一个状态被反复入队。5.2 DFS 实战拓扑排序、环检测、回溯搜索DFS 在很多算法里承担的是“探测”任务。比如检测无向图是否有环可以用 DFS 配合“父节点判断”如果 DFS 访问到邻居 vv 已经被访问过而且 v 不是当前节点的父节点就说明存在环。对于有向图则使用灰白黑三色标记灰节点存在环是关键信号。DFS 也是很多搜索类问题的基础。回溯法本质上就是在图上 DFS只不过这里的“图”通常是隐式的状态空间图。比如排列组合问题每个选择都生成一个新状态DFS 深入枚举所有可能到达边界再回溯撤销选择。这种场景反而要求每次递归返回后恢复 visited 状态因为你要的是所有满足条件的路径而不是单纯遍历完整个状态空间。拓扑排序用 DFS 实现时要注意输出的是逆序结果。一个比较稳的做法是在 DFS 函数的最后把当前顶点压入一个栈所有 DFS 结束后依次弹出得到的就是拓扑序。这个写法比递归后直接插入 vector 头部更高效因为 vector 头部插入是 O(n) 的而尾部插入或栈操作是 O(1) 的。5.3 两种遍历的复杂度对比一张表记心里面试时经常被问到 “BFS 和 DFS 的时间复杂度”答案取决于存储结构。存储结构BFS 时间复杂度DFS 时间复杂度空间复杂度邻接矩阵O(V^2)O(V^2)O(V^2)邻接表O(VE)O(VE)O(VE)为什么邻接矩阵是 O(V^2)因为每个顶点出队后都要扫描整整一行邻接关系即使这一行大部分都是 0。为什么邻接表是 O(VE)因为每个顶点入队或入栈一次每条边在遍历其某端点的邻居列表时被检查一次。空间复杂度方面最坏情况下 BFS 的队列可能包含一层所有顶点DFS 的递归栈或显式栈可能包含一条路径上所有顶点但整体上都不超过顶点数 V存储结构的空间开销起主导作用。6. 实际调试经验画出访问顺序比硬想代码更快最后分享一个我自己的调试习惯拿到题目或实际数据先手工画一个六个顶点以内的小图标好边然后按 BFS 或 DFS 的规则手动模拟一遍把访问顺序写下来再拿着这个顺序去对照代码输出。很多同学遇到代码结果不对第一时间是反复看代码逻辑但在我看来最有效的排查方式其实是拿一个小样例走一遍过程。我还喜欢在调试时把“当前队列/栈里的内容”打出来。比如 BFS 里每次出队后打印队列剩余元素DFS 的递归里可以打印当前顶点和它的邻居状态。虽然日常刷题不一定每次都要这么详细但遇到诡异问题时这个输出能快速帮你定位到一个很隐蔽的错误是不是某个邻居根本没有被放进图里或者边的方向反了。如果你想让这段代码真正变成自己的我建议不要只复制上面的模板。试着自己从零写一个完整程序包含一个五节点无向图、BFS 函数、DFS 函数再写一个可以不连通的全图循环。跑通之后再思考几个问题如果换成有向图代码要改哪里如果边带权重visited 还需要吗如果图是 10 万节点递归版 DFS 还扛得住吗这些问题想通了图遍历这一块基本就扎实了。我个人在实际操作中的体会是图的 BFS 和 DFS 并不难难的是把“存储结构 visited 时机 连通分量处理”这三件事同时想清楚。只要这三件事没有漏洞代码跑起来会非常安稳。那些写图遍历时反复出错的人几乎都能在这三个地方找到原因。希望这篇能帮你把图的遍历彻底理顺。