今天是2026年2月24日周二算法打卡第10天。这一轮复习的主题定在DFS、BFS和并查集三个放在一起复习是因为它们在解决“连通性、可达性、分组关系”这类问题上是三把互相呼应的钥匙很多题用DFS能做、用BFS也能做、换上并查集照样能AC。这种多解思路的对比比单纯刷一道题要值钱得多。这篇文章就是个人复习的记录和复盘我会把三个算法的套路、模板、梳理过的典型题、踩过的坑全部写出来。不管你是刚开始刷算法题的新手还是准备春招、实习面试的选手这篇内容都可以直接当复习提纲用。毕竟基本功这东西不练不行练了不复习约等于白练。1. 为什么把DFS、BFS、并查集放在一起复习1.1 三个算法的底层定位完全不同先理清一个基本认知DFS和BFS本质是遍历策略而并查集本质是数据结构。但是它们服务的问题是同一类——图或集合上的关系判断。DFS深度优先搜索的核心思路是一条路走到黑走不通了再回头换一条路靠递归或栈来维护状态。它适合做路径存在性判断、全排列、组合、子集、回溯搜索等题目优点是空间消耗小只保存当前路径缺点是可能绕远路找到的不一定是最短解。BFS广度优先搜索的核心思路是一层一层往外扩张像水波一样推进靠队列维护层级。它最大的优势是在无权图中第一次到达目标点时路径一定最短。但这个优势有代价空间复杂度明显高于DFS最坏情况下要保存一整层的节点。并查集则是处理动态连通性的利器。它只关心“两个节点是不是连在一起的”至于怎么连、路径是什么它不管。这种“模糊处理”让它在大规模连通性查询中的效率非常高配合路径压缩和按秩合并单次操作近乎常数级。1.2 从刷题角度看三者的互补关系我复习时做了个对比表把这几个算法放在同一类题上的表现列出来这样选型的时候大脑里就有了一张参照表问题类型DFS方案BFS方案并查集方案迷宫从起点到终点是否有路递归回溯可行但可能慢层序遍历首个到达即结束试错一般不适合找路求最短路径步数要配合剪枝容易超时最合适天然逐层推进无法直接获取路径长度判断两个节点是否连通每次都遍历复杂度高每次都遍历复杂度高最合适查询近乎O(1)无向图中找多余边可行但代码量偏多可做拓扑思路不直观最合适合并失败即为答案求连通分量个数遍历标记直观遍历标记直观合并集合统计根节点数量实际做题的过程中我发现很多题用DFS或BFS先写一遍再用并查集写第二遍对理解图结构非常有帮助。比如岛屿数量这道题用DFS染色的写法很顺手但用并查集硬刚一遍你就从一个全新的角度理解了“联通分量”这四个字。1.3 学习方法上的一点建议复习阶段不建议只盯着模板背更建议一个题用多种方法反复做。今天打卡我重点复刷了三个典型场景网格类DFS、树的层级BFS、还有经典的无向图冗余连接并查集。这样一次复习相当于覆盖了三种解题范式。另外我在每个算法下面都整理了可以直接套用的代码框架不是死记硬背而是让自己在赛场上可以“肌肉记忆”式地快速起手。下面进入正题。2. DFS复习递归框架、回溯剪枝与栈溢出处理2.1 递归版DFS模板这是基础中的基础DFS的最基本实现就是递归核心包含三要素终止条件、当前层处理、递归进入下一步有时带状态恢复。我在代码里习惯这样写void dfs(当前状态参数) { if (满足终止条件) { 记录结果; return; } for (所有可选择的下一步) { 做选择修改状态; dfs(下一步状态); 撤销选择恢复状态; // 回溯的关键 } }用全排列来举例这道题是DFS入门必刷题。给一个不含重复数字的数组返回所有可能的全排列class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); dfs(nums, used, path, res); return res; } void dfs(vectorint nums, vectorbool used, vectorint path, 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, used, path, res); path.pop_back(); used[i] false; // 状态恢复 } } };这个模板刷多了以后你会发现“撤销选择”那一行就是回溯的精髓。如果少了状态恢复你会在下一次分支里看到已经被使用过的元素导致结果全乱。我自己初学的时候就在这个位置上卡了好几次每次都是AC不过才反应过来忘记回溯了。建议每写一个DFS题第一时间检查三个位置终止条件对不对递归下一步参数传对了没回溯恢复完整不完整。2.2 网格类DFS方向数组与visited标记字符串、组合、排列之外的另一个高频DFS场景就是网格题最典型的是岛屿数量。这种题是二维矩阵上的DFS核心套路是使用方向数组来枚举上下左右四个方向class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int row grid.size(); int col grid[0].size(); int count 0; for (int i 0; i row; i) { for (int j 0; j col; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } void dfs(vectorvectorchar grid, int i, int j) { int row grid.size(); int col grid[0].size(); if (i 0 || i row || j 0 || j col || grid[i][j] 0) { return; } grid[i][j] 0; // 直接把访问过的陆地改成水省掉visited数组 dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } };这里有一个省事的技巧很多网格DFS题目可以直接在原数组上做标记把已访问的1改成0这样可以节省一个二维visited数组的空间。但是要注意如果你的业务逻辑里后续还需要用到原始数组千万不能这样就地修改记得复制一份或者用visited数组。我在实际刷题里最容易翻车的就是标记位置写错比如在进入递归前没标记递归完了又去标记导致重复访问陷入死循环。2.3 显式栈替代递归应对栈溢出递归虽然代码短但是有个致命弱点递归深度过大的时候函数调用栈会爆掉LeetCode上有些数据量大的题会直接报Stack Overflow。选项之一是改用显式栈来模拟递归。我常用这种写法来做不需要回溯的DFS// 用栈模拟网格DFS防止递归过深 void dfs_stack(vectorvectorchar grid, int startX, int startY) { stackpairint, int st; st.push({startX, startY}); grid[startX][startY] 0; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; while (!st.empty()) { auto [x, y] st.top(); st.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx grid.size() ny 0 ny grid[0].size() grid[nx][ny] 1) { grid[nx][ny] 0; st.push({nx, ny}); } } } }显式栈和递归式在思路上没有本质区别都是“后进先出”的顺序在推进。关键差异在于不需要维护系统调用栈可控性更好。遇到深度可能破万的情况比如树高度很大的遍历推荐用显式栈不然递归会把你坑得很惨。2.4 DFS中的剪枝优化复习到DFS就不得不提剪枝。全排列、组合这类问题数据量一旦上去暴力DFS一定超时这时候剪枝就是唯一的救星。剪枝分为可行性剪枝和最优性剪枝两类。可行性剪枝提前判断这条路继续走也不可能满足条件直接终止。比如组合总和问题中如果当前和已经大于目标值就没必要继续递归了。最优性剪枝搜索过程中如果发现当前路径的代价已经不小于已知最优解直接放弃。这在DFS求解最优化问题时格外重要。一个常用的小技巧是递归参数里把当前累计值传进去在进入下一层之前就先判断是否超限。这样可以避免做无用功典型场景就是N皇后、数独、组合求和。剪枝写完以后一定要测试边界数据不然剪错枝会把正确答案也剪掉这种情况我踩过不止一次。3. BFS复习队列模板、层级控制与双向BFS优化3.1 标准BFS模板有序推进是关键BFS的核心数据结构是队列每次循环都要把当前层的所有节点一次性处理完。模板长这样void bfs(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 当前层节点数非常重要 for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); // 处理当前节点 if (node-left) q.push(node-left); if (node-right) q.push(node-right); } // 当前层处理完毕可以在这里记录层数 } }这个模板里面的int size q.size()是BFS分层的关键。如果不预先记录size直接while (!q.empty())来写队列会不断加入下一层节点就无法区分当前层和下一层的边界了。求最短路径、层序遍历这类题目都需要依赖这个分层技巧我建议直接把这一行背进肌肉里。3.2 二叉树层序遍历的完整实现二叉树层序遍历是BFS最经典的入门题要求和这道题也刚好切合今天复习的主题。直接给一个标准写法class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; } };注意这里有一个很容易出错的点for (int i 0; i size; i)和for (int i 0; i q.size(); i)是有本质区别的。后者在每层入队以后q.size()会动态变化相当于遍历了所有还没处理的节点层边界就全乱了。所以先把size取出来这个习惯最好从一开始就养好。3.3 网格BFS求最短路径为什么BFS能保证最短在无权图中BFS第一次到达终点时的层数就是最短距离这个性质是DFS不具备的。原因很好理解BFS按层推进第k层处理完以后接下来面临的就是所有距离起点为k1的节点不存在“绕远路先到”的可能。求迷宫最短路径的模板通常配合一个距离数组或者visited数组来标记每个格子是从起点走几步到的int bfsShortestPath(vectorvectorint maze, pairint,int start, pairint,int end) { int m maze.size(), n maze[0].size(); vectorvectorint dist(m, vectorint(n, -1)); queuepairint,int q; q.push(start); dist[start.first][start.second] 0; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x end.first y end.second) { return dist[x][y]; } for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx m ny 0 ny n maze[nx][ny] 0 dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } return -1; // 无法到达 }这个写法里的dist[nx][ny] -1其实同时起到了visited数组的作用判断这个格子是否被访问过顺便还记录了步数。这是一种很省空间的技巧以后碰到网格最短路题目可以优先这么写。dist[起点]0之后每个新格子的距离都等于上一格的距离加一这个递增公式就是BFS求最短路的根基。3.4 双向BFS把搜索空间开根号BFS在大数据量场景下一个常见优化是双向BFS从起点和终点同时开始搜索两边交替一层层扩展直到两个方向在中间相遇。这个思路可以把搜索树的高度直接砍一半效果非常明显。单词接龙、走迷宫这类题单向BFS会超时换成双向BFS往往一秒过。我写双向BFS的习惯是准备两个哈希集合分别存从起点和终点出发已经访问到的当前层节点int bidirectionalBFS(unordered_setstring startSet, unordered_setstring endSet, unordered_setstring dict) { unordered_setstring visited; int step 0; while (!startSet.empty() !endSet.empty()) { // 每次扩展较小的那一层减少搜索量 if (startSet.size() endSet.size()) { swap(startSet, endSet); } unordered_setstring nextLevel; for (string word : startSet) { // 遍历所有可能的下一步变化 // 如果变化后的词也在 endSet 中说明相遇返回 step 1 // 如果变化后的词在 dict 且没访问过加入 nextLevel } startSet nextLevel; step; } return -1; }有一个实际体会想特别说一下双向BFS的终止条件判断要及时。每次扩展完一层后都要立刻检查新的集合和另一端的集合是否有交集如果有交集就结束。忘记检查交集或者检查晚了会导致搜索范围扩大一圈优化效果就大打折扣了。3.5 BFS和A*算法怎么选热搜里也有人搜“A算法与BFS的优缺点”这个正好可以复习时一起补充。BFS适合无权图、边权相等的最短路径问题实现简单、结果最优。A算法则适合有权图、带启发信息的搜索通过估价函数f(n)g(n)h(n)来引导搜索方向效率往往更高但代价是需要设计合理的启发函数代码复杂度更高。如果题目给的是一个普通网格且每步代价相同直接用BFS就好没必要上A*。如果路径代价不一致或者地图很大A*可能更合适。4. 并查集复习连通性判断的利器4.1 并查集要解决什么问题先说个场景朋友圈里两个人之间是好友好友的好友也算间接朋友。给你很多组好友关系要判断两个人是否在同一个朋友圈或者统计有几个朋友圈。这种“动态连接即时查询”的问题用DFS或BFS做的话效率很低因为每次查询都要重新遍历一遍。并查集就是为这种场景而生的数据结构。并查集的两大核心操作是查找Find和合并Union。查找找到一个节点所在集合的代表元素根节点合并把两个不同集合的代表元素通过指向关系合并成一个集合4.2 从朴素实现到路径压缩再到按秩合并先写一个最朴素的并查集框架class UnionFind { private: vectorint parent; public: UnionFind(int n) { parent.resize(n); for (int i 0; i n; i) { parent[i] i; // 初始时每个节点的根是自己 } } int find(int x) { while (parent[x] ! x) { x parent[x]; } return x; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 把x的根指向y的根 } } bool isConnected(int x, int y) { return find(x) find(y); } };这个版本的find是O(n)的一旦树退化成链表性能会非常差。优化一路径压缩让find过程中经过的每个节点都直接指向根节点int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; }路径压缩做完以后其实树的高度基本被压到只有一两层find操作接近O(1)。但还有一种情况会让性能不一致合并时如果不加考虑总是把一棵大树接在小树上或者把高树接在矮树上树还是可能退化。优化二按秩合并合并时让高度较低的树接到高度较高的树下面class UnionFind { private: vectorint parent; vectorint rank; public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } };路径压缩加按秩合并这两个优化都加上以后并查集单次操作的均摊时间复杂度是O(α(n))其中α(n)是反阿克曼函数。这个函数增长极其缓慢在实际数据范围内基本可以看作是常数。所以并查集是大规模连通性问题的绝佳选择。4.3 冗余连接并查集最经典的实战题这道题是LeetCode 684题意是给一棵树额外加一条边导致出现环要求找出一条可以删除的边使得删除后还是一棵树。并查集的解法思路非常直接遍历每一条边如果两个端点已经在同一个集合里说明这条边会造成环它就是答案。class Solution { public: vectorint findRedundantConnection(vectorvectorint edges) { int n edges.size(); vectorint parent(n 1); vectorint rank(n 1, 0); for (int i 0; i n; i) parent[i] i; for (auto edge : edges) { int u edge[0], v edge[1]; if (find(parent, u) find(parent, v)) { return edge; } unite(parent, rank, u, v); } return {}; } int find(vectorint parent, int x) { if (parent[x] ! x) { parent[x] find(parent, parent[x]); } return parent[x]; } void unite(vectorint parent, vectorint rank, int x, int y) { int rootX find(parent, x); int rootY find(parent, y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } };这题看起来很巧妙但如果你理解并查集的核心思想就会发现这其实是一个非常自然的解法。每加入一条边就合并两个端点如果两个端点本就已经在一个集合中说明它们之前已经存在一条通路再加一条边就必然成环。复习到这个地方时我强烈建议你亲手在纸上模拟一遍整个过程对理解“集合连通性”特别有帮助。4.4 并查集的其他应用场景除了冗余连接并查集还常出现在这些题目里统计无向图中连通分量的个数合并所有边后统计根节点数判断两个节点是否连通配合在线查询按权值排序的边逐步合并判断连通性Kruskal最小生成树算法底层就是并查集带权并查集可以维护节点到根节点的距离解决种类划分、偏移量问题我在复习时额外看了一遍带权并查集虽然这次打卡没深入题目但知道有这种扩展方向以后遇到题才不慌。5. 常见问题与排查技巧实录5.1 DFS老超时、老爆栈怎么办DFS最常见的两个问题正是超时和爆栈。超时大概率是因为没有剪枝或者没有用visited数组去重。比如求组合总和时数据大、目标值大不剪枝必然TLE。建议每次写完DFS都问自己一句“这里有没有可能提前终止的路径有没有已经访问过的节点被重复访问”爆栈多半是递归深度太大。LeetCode上很多迷宫的测试数据规模很大递归深度可能达到上万层这时候系统栈直接撑不住。解决办法是改用显式栈或者提前计算递归深度必要时用BFS重写。5.2 BFS调试中的常见坑BFS里我遇到最多的坑是忘记分层导致的逻辑错误。如果题目不需要返回最短步数只判断是否可达那不分层没问题。但一旦要统计步数、层数就必须在进入while循环前取好size。另一个坑是visited数组标记时机晚了一步。在push进队列的时候就应该标记visited而不是在pop出来的时候再标记。如果在pop时标记同一个节点可能被多个邻居同时push进队列导致队列里出现大量重复节点空间和时间都白白浪费。5.3 并查集容易犯的低级错误第一find写成了非递归但没做路径压缩数据量一大还是会超时。第二unite时没有先查找两个根节点是否相同就直接连接可能导致出现环。第三初始化时parent数组大小搞错特别是有的时候节点编号从0开始、有的从1开始边界问题容易弄反。我自己还有一个习惯在写并查集的unite方法之前总是先find一次拿到两个root再做判断这样可以避免后续逻辑混乱。5.4 三算法问题排查速查表现象可能原因排查方向DFS结果重复忘记回溯、状态恢复不完整检查撤销选择的逻辑DFS超时缺少剪枝、树高度过大加可行性剪枝、是否可改BFSDFS爆栈递归深度太大改显式栈、增大栈空间BFS步数多了size分层时机错误确认取size的位置在进入队列前BFS死循环visited标记过晚或没标记在入队时立即标记visited并查集查询慢没有路径压缩改写递归版压缩路径并查集合并错误没先find根再操作在unite里先调find6. 一些复习心得和打卡建议第10天打卡完成这次回顾让我重新意识到一个问题算法题的熟练度是需要反复刺激的。比如并查集可能一个月前很熟一个月不写就生疏了。即使是今天复刷的模板再过一个星期不碰又得翻代码才能想起来。所以复习的节奏比学新题的节奏还要重要。我个人比较受用的方式是每天固定时间先花10分钟默写一遍三个算法的核心模板再去做题。这样下来模板成了肌肉记忆考试和面试时不需要硬想自然就能写出来。另外每道题做完之后不要马上看题解先自己把代码跑几组例子再翻题解对照。我跟别人交流时发现很多人刷题一味追求数量今天DFS十道、明天BFS十道但一个星期以后再回头看这些题全都忘了。慢一点、精一点把一道题用三种方法做明白比囫囵吞枣做十道题有价值得多。最后再分享一个小习惯我会在一个专门的复习文档里把每道题的代码、思路、复杂度、甚至踩坑记录都汇总在一起相当于自己的算法错题本。今天这次打卡的内容也打算一并归档进去。等以后再遇到类似的题直接翻出来对照复习效率会高很多。