DFS、BFS与并查集：图论三大核心算法实战解析

1. 为什么把 DFS、BFS、并查集放在同一天复习今天周二算法打卡第 10 天。翻了下前面的打卡记录链表、栈、队列、二分、贪心轮了一遍今天到了图论这个坎。我特意把 DFS、BFS、并查集三个一起复习不是随手凑数是因为这三兄弟在面试和比赛里出现的频率实在太高而且它们之间是互联互通的关系。很多题你用 DFS 能解换 BFS 也能解再换个思路用并查集照样能解区别只是时间空间复杂度不同、代码风格不同、以及你对哪种写法更有把握。先说结论DFS 和 BFS 解决的是怎么遍历的问题并查集解决的是谁和谁连通的问题。听起来好像是两码事但实际刷题的时候它们的边界经常交叉。比如一个二维网格题问你有几个岛屿——DFS 可以从一个格子出发把所有相邻的 1 都标记掉BFS 可以一层一层往外扩散并查集可以把相邻的 1 全部 union 到一个集合里然后数根节点个数。三个做法都对但你至少要熟练掌握其中两个才能在笔试那种紧张状态下顺手写出来。另外从面试的角度看这三块几乎就是图论题目的半边天。LeetCode 上搜 DFS 相关题有三百多道BFS 两百多道并查集虽然少一些但也有近一百道。更重要的是它们经常作为前置知识和其他算法组合比如拓扑排序基于 BFS/DFSTarjan 求强连通分量依赖 DFSKruskal 最小生成树依赖并查集。如果这几个基础不牢后面那些高级算法全都是空中楼阁。所以今天的复习思路是这样先把每个算法的核心逻辑和标准模板捋一遍再用几道典型题目把三个算法串起来最后总结这几天刷题踩过的坑。这篇文章不追求把每个算法的所有边角料都讲完而是把最重要的骨架和最容易出错的地方讲透。2. DFS递归树、回溯与剪枝的三板斧2.1 先把 DFS 想成一棵递归树而不是一条路走到黑很多人学 DFS 的时候脑子里只有一个模糊的印象——往深处走走不动了再回来。这个说法没错但它太抽象了真正做题的时候你会发现自己根本不知道哪儿是深处走不动了该怎么回来。我的理解方式是把 DFS 看成一棵决策树。比如你要在一个二维网格里找一条从起点到终点的路径每一步你有上下左右四个选择每个选择都生成一个新的分支把所有分支画出来就是一棵树。DFS 就是拿一把深度优先的扫描仪一个分支一个分支地去尝试每次走到树叶边界或死路就回头换个分支再走。这个视角对写代码非常关键。因为一旦你意识到DFS 就是遍历一棵隐式树你写递归函数的时候就知道自己需要哪三样东西当前状态参数、递归终止条件、如何生成下一步的状态邻居/分支。有了这个框架不管题目是迷宫、排列组合、还是括号生成你都能套进去。我复习的时候习惯先画图再写代码。哪怕是已经见过的题我也先在草稿纸上把递归树的前三层画出来确认终止条件和分支顺序再动手写。这个习惯帮我省了不少调试时间。2.2 标准模板递归函数、visited 标记、回溯恢复现场DFS 的标准模板没什么花哨的核心就三个部分。以在一个二维矩阵中遍历为例#include vector using namespace std; const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void dfs(vectorvectorint grid, int x, int y, vectorvectorbool visited) { int rows grid.size(); int cols grid[0].size(); // 1. 边界检查 访问检查 if (x 0 || x rows || y 0 || y cols) return; if (visited[x][y]) return; // 2. 处理当前节点 visited[x][y] true; // ... 对当前格子的具体操作比如累加计数、判断是否为目标态 // 3. 递归遍历四个方向 for (int d 0; d 4; d) { int nx x dirs[d][0]; int ny y dirs[d][1]; dfs(grid, nx, ny, visited); } }注意这里有一个容易被新手忽略的点visited 数组的标记位置。正确的位置是进入递归函数后第一时间判断并标记而不是在 for 循环里调用下一层递归之前才标记。如果你在 for 循环里先判断!visited[nx][ny]再递归而递归进去的第一行又判断了一遍 visited逻辑上也没错但代码就冗余了。我见过不少同学两种写法混着来最后 debug 的时候反复查为什么某些格子重复访问其实就是标记时机不统一。再来看一个更完整的回溯模板——比如生成全排列#include vector #include algorithm void dfs(vectorint nums, vectorint path, vectorbool used, vectorvectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); dfs(nums, path, used, res); // 回溯撤销选择恢复到进入递归前的状态 path.pop_back(); used[i] false; } }这段代码里最关键的是最后两行path.pop_back()和used[i] false。这就是恢复现场。为什么必须恢复因为 DFS 递归的所有分支共用同一份path和used如果你不在返回时把当前分支做出的修改撤销掉下一个分支看到的就是被污染的现场所有排列都会乱掉。我第一次写全排列的时候就是忘掉了回溯恢复结果同一个组合出现了无数次还有个巨大的难受点代码逻辑看着没问题就是结果错。后来我才意识到回溯的本质就是你从哪条路来的回去的时候要把脚印擦掉这样才能保证另一条路的起点跟之前一样。2.3 剪枝不是优化而是解题的必要手段剪枝这个词听起来很高端其实就是提前知道这条路走不通就不浪费时间去走了。DFS 的复杂度随分支数指数增长如果题目数据范围稍微大一点不剪枝就是死路一条。常见剪枝有两种可行性剪枝和最优性剪枝。可行性剪枝是提前判断当前状态之后是否还能达到目标状态。比如在往下走之前判断剩下的步数够不够到终点不够就不递归了。最优性剪枝一般用在求最优解的场景比如当前已走的路径长度已经大于目前找到的最优解直接放弃继续探索。我自己的经验是剪枝不是写完全部代码之后再慢慢加的而是想清楚递归树长什么样的时候顺便就想清楚哪些分支根本不用生成。这样你写的递归函数天然就带剪枝逻辑而不是后期打补丁。有同学可能会说刷题的时候先把朴素版本写出来能过就过过不了再剪枝。我的建议是笔试的时候可以这么干因为时间紧。但如果是日常训练一定要刻意练习先剪枝再递归的思考方式。因为面试官经常问的是这个 DFS 的时间复杂度是多少为什么能剪枝如果你答不出底层逻辑就露馅了。3. BFS队列、分层控制与最短路的三件套3.1 BFS 为什么天然适合求无权图最短路DFS 擅长的是能不能到和有哪些路径BFS 擅长的是最少走几步才能到。只有一字之差但原理完全不同DFS 是一条路走到黑BFS 是一圈一圈往外扩。因为 BFS 的扩展顺序是按照和起点的距离一层一层推进的所以第一次遇到目标节点时走过的层数一定是最少的这就是无权图最短路。这个第一次碰到就是最优的性质是 BFS 区别于 DFS 的核心卖点。你不需要在所有路径里比较长度不需要剪枝只要保证 BFS 的层序正确答案自然就出来了。举个最常见的例子在迷宫中从起点到终点最少走几步。DFS 也可以做但你需要搜完全部路径才能比较出最短的一条而 BFS 只要搜到终点就收工思维量完全不同。3.2 两种分层写法size 快照法和 dist 数组法BFS 的标准结构是队列 visited 数组这个很多人知道。但写的时候有一个关键点你想知道当前走的是第几层就必须在每一层开始之前记录当前队列中元素的数量。size 快照法长这样#include queue #include vector using namespace std; int bfs(vectorvectorint grid, int startX, int startY, int targetX, int targetY) { const int dirs[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int rows grid.size(), cols grid[0].size(); vectorvectorbool visited(rows, vectorbool(cols, false)); queuepairint, int q; q.push({startX, startY}); visited[startX][startY] true; int steps 0; while (!q.empty()) { int size q.size(); // 关键当前层节点数 for (int i 0; i size; i) { auto [x, y] q.front(); q.pop(); if (x targetX y targetY) return steps; for (int d 0; d 4; d) { int nx x dirs[d][0]; int ny y dirs[d][1]; if (nx 0 || nx rows || ny 0 || ny cols) continue; if (visited[nx][ny] || grid[nx][ny] 1) continue; visited[nx][ny] true; q.push({nx, ny}); } } steps; } return -1; }dist 数组法则是在每个节点上记一个从起点走到这里需要几步入队的时候就更新邻居的 dist返回目标节点的 dist 即为最短路。两种写法殊途同归我个人的偏好是如果题目最终要的是步数用 size 快照法更直观如果题目还要求记录路径或者有多种代价用 dist 数组法更容易扩展。3.3 双向 BFS把指数级搜索空间砍掉一半层数多了以后 BFS 也会慢因为搜索空间是按层数指数增长的。双向 BFS 的思路是从起点正向搜索同时从终点反向搜索两边各走几步在中点汇合。这样搜索的规模从单边指数的两层变成两边各自只有原来一半的深度整体效率提升非常可观。我拿单词接龙这类题来举例。假设单词长度 L词典大小 N正向 BFS 从起点扩展到终点可能要扩展很多层但如果你同时从终点反向扩展两边各走到第 maxStep/2 层就能碰头。实际写双向 BFS 的时候有个小技巧每次扩展时优先扩展当前队列较短的哪一边让两边规模尽量均衡。这个优化实现起来不难但对性能提升明显。关于双向 BFS 我特别想说不要被它的名字吓到其实代码结构和普通 BFS 非常接近。你只需要两个队列、两个 visited 集合或数组每次 while 循环里处理当前层节点数量较少的那一边直到两个 visited 集合出现交集。只需要理解从两边同时逼近代码自己推一遍就能写出来。4. 并查集从 Quick-Find 到按秩合并的演进之路4.1 并查集到底解决了什么问题并查集这个数据结构说白了两件事查两个元素是否在同一个集合里合并两个元素所在的集合。这里的集合在多数题里都是连通分量的意思——比如两个网络节点之间是否有路径可达、两个社交账号是否属于同一个圈子、两个格子是否属于同一个岛屿。我第一次接触并查集的时候觉得它是一个很高冷的数据结构代码就那么十行但看不出为什么要这么设计。直到后来刷冗余连接这道题才真正开窍你在一个图里逐条加边每条边把两个节点 union 起来如果在某次 union 时发现这两个节点已经在同一个集合里了说明这条边就是冗余边——形成环的那条边。这种动态维护连通性的操作并查集几乎是唯一好写的解法。4.2 从朴素实现到路径压缩核心就是两段代码并查集最经典的实现是森林 父指针数组。每个集合是一棵树树的根就是集合的代表元素。find(x)返回 x 所在集合的根节点union(x, y)把 x 所在树和 y 所在树合并。初学时你可以三步走。第一步最简单parent数组存每个节点的父节点find循环向上走找到根union把一个根挂到另一个根上。这种朴素实现在链状结构下查找是 O(n) 的太慢。第二步是路径压缩。在find的过程中顺手把沿途所有节点直接挂到根节点下面让树的形状变扁平。代码就一行int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; }这个递归版本简洁优雅但要注意如果并查集的规模非常大递归可能爆栈所以也有迭代版本int find(int x) { int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; }第三步是按秩合并。union 的时候把树高度较小的树挂到较大的树下面避免树越来越高。如果是用集合大小做秩也能达到类似效果。4.3 三版并查集模板对比与工程选型我把三个版本的并查集整理成一张表方便你在面试前快速过一遍实现版本find 复杂度union 复杂度适用场景代码量朴素数组O(n)O(n)教学理解数据量极小约 10 行路径压缩O(α(n)) 均摊O(α(n))大多数竞赛/面试题目约 12 行路径压缩 按秩合并O(α(n)) 均摊O(α(n))工程级场景避免退化约 18 行这里 α(n) 是反阿克曼函数你可以直接理解成常数级别。也就是说路径压缩之后的并查集amortized 时间复杂度基本是 O(1)非常快。到了这个程度并查集的性能几乎不是瓶颈真正考验你的是什么时候该用并查集。一个判断标准是题目里是否存在不断合并集合、并且随时询问两个元素是否在同一集合的操作。如果有八成就是用并查集。反过来如果所有边都是预先给定的、一次性建图那 DFS/BFS 或拓扑排序可能更适合不需要动态维护。4.4 带权并查集进阶选手可以吃的第一口补品如果普通并查集的题目你已经写得滚瓜烂熟可以试试带权并查集。所谓权就是元素和其父节点之间的某种关系值比如x 比 y 大几岁x 到 y 的距离是多少。核心思想是 find 时除了更新父指针还要累加/更新权值union 时也要根据两个集合根之间的数值关系调整权值。带权并查集解决的问题比如给定若干条 a 比 b 多多少的信息判断是否矛盾——这种题笔试偶尔出现面试问到的概率不高。我的建议是基础并查集没完全吃透之前不用急着碰带权版本。先把 4.2 的模板背熟再做几道经典题再决定要不要深入。5. 三类经典题型的解法联动同一个题三种思路5.1 岛屿数量DFS、BFS、并查集各来一遍这道题是图论入门的必修课也是检验 DFS/BFS/并查集掌握程度的最佳试验场。题面很直白二维矩阵中 1 表示陆地0 表示水上下左右相邻的 1 算同一个岛问总共有几个岛。DFS 的思路是最直接的遍历每个格子遇到没访问过的陆地就计数加一然后用 DFS 把这一整块陆地全部标记成已访问。BFS 版就是把 DFS 里的递归改成队列层级扩散。并查集版则把所有陆地格子做 union 操作最后统计有多少个陆地格子的根是自己。三种方法的时间复杂度都是 O(m×n)空间复杂度也差不多区别在于代码风格。我个人实际经验是笔试手写的时候 DFS 最不容易出错代码最短BFS 次之适合那些怕递归爆栈的场景并查集代码略长但它在矩阵特别大、且需要多次查询连通性的场景下更有优势。建议三道题乐扣 200 岛屿数量、130 被围绕的区域、990 等式方程的可满足性用三种写法分别刷一遍刷完你对三个算法的理解会上升一个台阶。5.2 被围绕的区域从边界反向 BFS/DFS比正向处理简单一个量级这道题题面把矩阵中被 X 包围的所有 O 变成 X如果在边界的 O 及其相连的 O 则保持不变。第一次做的时候很多人的直觉是从每个 O 出发做 DFS/BFS判断是否接触边界再决定要不要翻转。这个思路能通但实现起来要额外处理状态标记、防止重复扫描很烦。更优的做法是逆向思维只从矩阵边界上的 O 出发做 DFS/BFS/并查集把所有能到达的 O 标记为安全。最后遍历全图安全 O 保留其他 O 全部改成 X。这个思路之所以好用是因为把判断被包围变成了判断不被包围两者的搜索空间完全不同。边界点数量远小于全图 O 的数量而且不需要反复来回扫描。这道题给我最大的启发是算法的难点往往不只是代码本身更是你能不能找到一个更省力的扫描顺序。正向遍历全图每个 O 都跑一遍搜索和只从边界反向标记一遍效果一样但工作量天差地别。5.3 冗余连接并查集在找环场景下的一招鲜冗余连接题面一个 n 个节点的有向图/无向图去掉一条边后能变成一棵树让你找出那条应该被去掉的边。面试常考题解法就是并查集。逐条遍历边union边的两个端点。如果在某条边的 union 之前发现两个端点已经在同一个集合里说明这条边是多余的——因为它连接的两个点之前已经通过其他路径连在一起了再加上这条边就形成环。对于无向图版本这条边就是答案对于有向图版本还要额外考虑入度问题但思想一致。这个题最值得玩味的是如果你用 DFS 去想得搭一个图、跑一遍拓扑或环检测代码量不小。而并查集版本只需要十几行思路还特别直白。这就是我强调同一个题先多想想能不能用并查集的原因——它经常能把一道看起来需要建图的难题降维成一个简单的循环加 union。5.4 矩阵中的最短路径BFS 实战演练网格走迷宫这类题我建议用 BFS 练手。你需要在 BFS 的每一层记录步数同时处理障碍物和 visited。这类题最容易错的地方是入队的时候没有立刻标记 visited导致同一节点被重复入队然后在层数统计上出错。正确的姿势是一旦决定入队就立刻在 visited 数组上标记这样能保证每个节点只入队一次。很多 BFS 迷宫的代码里steps的位置不一样结果也会不一样。建议在 while 循环开始前把当前队列长度存到一个变量里先处理完当前层的所有节点再steps。这样可以保证起点本身是第 0 层第一次到达目标点返回的 steps 恰好就是最短步数。我之前就是在这个细节上栽过跟头少走了好几层但自己完全不知道最后对拍答案才找出来。6. 打卡两周踩过的坑与复盘写到这里我想把这几周刷题时踩过的坑集中梳理一下。这些坑不算玄学但经常在关键时刻浪费宝贵的笔试时间。第一个坑是递归爆栈。DFS 在数据量大的时候系统栈可能不够用特别是 C 用默认栈设置时容易出现栈溢出。比赛或者笔试里如果明确矩阵规模很大建议优先考虑 BFS或者把递归 DFS 改成显式栈的迭代 DFS。Python 的话注意sys.setrecursionlimit但这只是延缓爆栈不是根治。第二个坑是 visited 数组标记的时机。我在 3.2 已经强调过BFS 一定要在入队的时候标记而不是出队的时候标记。否则同一层会有大量重复节点入队不仅浪费空间还可能导致步数统计错误。DFS 则在进入节点后第一件事就标记不要拖到 for 循环里。第三个坑是并查集的初始化。parent数组初始化的时候每个元素都指向自己。这个环节太基础好多人容易手滑写出parent[i] i - 1之类的错。一旦初始化错了后面所有 find/union 全崩而且报错信息不明显很难排查。我给自己定的规矩是写并查集的第一件事是先单独跑一个小样例验证所有节点的 find 结果都是自己。第四个坑是路径压缩的代价。路径压缩确实让并查集变快但它会破坏树的高度信息所以在需要知道集合大小或需要按秩合并的场景下不能只用路径压缩而忽略 size/rank 数组的同步维护。很多人只知道压缩路径可以加速却不知道如果题目要求合并后统计每个集合的元素个数压缩路径后还得单独维护 sz 数组union 时把 sz 累加。第五个坑是矩阵题的边界处理。DFS/BFS 里四个方向的邻居很容易写出越界访问尤其是坐标 1/-1 的地方。我的经验是先把边界检查写在递归函数开头而不是写在生成邻居的地方这样写出来的代码更不容易漏。如果是在 leetcode 上刷题错误信息会告诉你越界但笔试的本地环境通常没有这种提示一旦越界就是段错误很难排查。第六个坑是读错题。之前说过四个方向 vs 八个方向的问题这不算算法难但真的很容易看漏。还有区分求最短路径还是判断是否能到达——前者优先 BFS后者 DFS/BFS 都可。我这两周大概有 20% 的错误不是算法写错而是题目理解错。建议每次拿到题目先把输入输出样例吃透再多花 30 秒想一想这个题最直接的解法是什么不要上来就开码。7. 复习之后的一点私人心得三块内容写完之后我脑子里其实冒出一个感受算法复习这件事最忌讳的是我全都会的错觉。看题解看懂了不叫会关了题解能默写模板、能讲清楚边界 case 怎么处理才叫真会。所以我这几天的打卡模式都是白天先做题晚上把当天用到的模板抄一遍再对着空白页面手写一遍中间哪里卡住了哪里就是你的薄弱点。拿 DFS 来说我一开始也觉得自己会写了几天全排列之后才发现回溯里的恢复现场我总是忘记而且不同题目的状态表示变化极大——有时候是修改数组值有时候是改变 bool 标记有时候是往 path 里 push 再 pop。如果只是背套路不亲自写几道很难意识到这些细节的共性。对于正在刷题打卡的朋友我特别想分享一个笨但有效的方法所有模板不要只抄一遍每隔三到五天回头默写一遍默写不出来就重新梳理逻辑。我自己把 DFS、BFS、并查集这三个模板反复默写了五六遍到后来哪怕凌晨脑子不太清醒也能一口气写对。这个习惯帮我在几次模拟笔试里省下了大量 debug 时间。最后啰嗦一句今天的打卡标题是复习算法DFS BFS 并查集但真正的收获不是背下了几个模板而是理解了什么时候该用哪个、用的时候要注意什么。这些经验是你主动踩坑、主动复盘换来的别人讲一百遍都不如自己动手写一遍。如果你也在刷算法希望今天这篇能帮你少走几个我走过的弯路那就值了。