DFS、BFS与并查集核心模板详解：连通性问题的三把钥匙

今天是2026年2月24日，周二，算法打卡第10天。这一轮复习的主题定在DFS、BFS和并查集，三个放在一起复习，是因为它们在解决“连通性、可达性、分组关系”这类问题上是三把互相呼应的钥匙，很多题用DFS能做、用BFS也能做、换上并查集照样能AC。这种多解思路的对比，比单纯刷一道题要值钱得多。

这篇文章就是个人复习的记录和复盘，我会把三个算法的套路、模板、梳理过的典型题、踩过的坑全部写出来。不管你是刚开始刷算法题的新手，还是准备春招、实习面试的选手，这篇内容都可以直接当复习提纲用。毕竟基本功这东西，不练不行，练了不复习，约等于白练。

1. 为什么把DFS、BFS、并查集放在一起复习

1.1 三个算法的底层定位完全不同

先理清一个基本认知：DFS和BFS本质是遍历策略，而并查集本质是数据结构。但是它们服务的问题是同一类——图或集合上的关系判断。

DFS（深度优先搜索）的核心思路是一条路走到黑，走不通了再回头换一条路，靠递归或栈来维护状态。它适合做路径存在性判断、全排列、组合、子集、回溯搜索等题目，优点是空间消耗小（只保存当前路径），缺点是可能绕远路，找到的不一定是最短解。

BFS（广度优先搜索）的核心思路是一层一层往外扩张，像水波一样推进，靠队列维护层级。它最大的优势是在无权图中第一次到达目标点时，路径一定最短。但这个优势有代价，空间复杂度明显高于DFS，最坏情况下要保存一整层的节点。

并查集则是处理动态连通性的利器。它只关心“两个节点是不是连在一起的”，至于怎么连、路径是什么，它不管。这种“模糊处理”让它在大规模连通性查询中的效率非常高，配合路径压缩和按秩合并，单次操作近乎常数级。

1.2 从刷题角度看三者的互补关系

我复习时做了个对比表，把这几个算法放在同一类题上的表现列出来，这样选型的时候大脑里就有了一张参照表：

实际做题的过程中我发现，很多题用DFS或BFS先写一遍，再用并查集写第二遍，对理解图结构非常有帮助。比如岛屿数量这道题，用DFS染色的写法很顺手，但用并查集硬刚一遍，你就从一个全新的角度理解了“联通分量”这四个字。

1.3 学习方法上的一点建议

复习阶段不建议只盯着模板背，更建议一个题用多种方法反复做。今天打卡我重点复刷了三个典型场景：网格类DFS、树的层级BFS、还有经典的无向图冗余连接（并查集）。这样一次复习，相当于覆盖了三种解题范式。

另外，我在每个算法下面都整理了可以直接套用的代码框架，不是死记硬背，而是让自己在赛场上可以“肌肉记忆”式地快速起手。下面进入正题。

2. DFS复习：递归框架、回溯剪枝与栈溢出处理

2.1 递归版DFS模板，这是基础中的基础

DFS的最基本实现就是递归，核心包含三要素：终止条件、当前层处理、递归进入下一步（有时带状态恢复）。我在代码里习惯这样写：

void dfs(当前状态参数) { if (满足终止条件) { 记录结果; return; } for (所有可选择的下一步) { 做选择，修改状态; dfs(下一步状态); 撤销选择，恢复状态; // 回溯的关键 } }

用全排列来举例，这道题是DFS入门必刷题。给一个不含重复数字的数组，返回所有可能的全排列：

class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> path; vector<bool> used(nums.size(), false); dfs(nums, used, path, res); return res; } void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& 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(vector<vector<char>>& 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(vector<vector<char>>& 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(vector<vector<char>>& grid, int startX, int startY) { stack<pair<int, 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; queue<TreeNode*> 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: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (!root) return res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); vector<int> 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层处理完以后，接下来面临的就是所有距离起点为k+1的节点，不存在“绕远路先到”的可能。

求迷宫最短路径的模板，通常配合一个距离数组或者visited数组来标记每个格子是从起点走几步到的：

int bfsShortestPath(vector<vector<int>>& maze, pair<int,int> start, pair<int,int> end) { int m = maze.size(), n = maze[0].size(); vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int,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_set<string>& startSet, unordered_set<string>& endSet, unordered_set<string>& dict) { unordered_set<string> visited; int step = 0; while (!startSet.empty() && !endSet.empty()) { // 每次扩展较小的那一层，减少搜索量 if (startSet.size() > endSet.size()) { swap(startSet, endSet); } unordered_set<string> 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: vector<int> 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: vector<int> parent; vector<int> 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: vector<int> findRedundantConnection(vector<vector<int>>& edges) { int n = edges.size(); vector<int> parent(n + 1); vector<int> 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(vector<int>& parent, int x) { if (parent[x] != x) { parent[x] = find(parent, parent[x]); } return parent[x]; } void unite(vector<int>& parent, vector<int>& 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 三算法问题排查速查表

6. 一些复习心得和打卡建议

第10天打卡完成，这次回顾让我重新意识到一个问题：算法题的熟练度是需要反复刺激的。比如并查集，可能一个月前很熟，一个月不写就生疏了。即使是今天复刷的模板，再过一个星期不碰，又得翻代码才能想起来。所以复习的节奏比学新题的节奏还要重要。

我个人比较受用的方式是每天固定时间，先花10分钟默写一遍三个算法的核心模板，再去做题。这样下来，模板成了肌肉记忆，考试和面试时不需要硬想，自然就能写出来。

另外，每道题做完之后，不要马上看题解，先自己把代码跑几组例子，再翻题解对照。我跟别人交流时发现，很多人刷题一味追求数量，今天DFS十道、明天BFS十道，但一个星期以后再回头看，这些题全都忘了。慢一点、精一点，把一道题用三种方法做明白，比囫囵吞枣做十道题有价值得多。

最后再分享一个小习惯：我会在一个专门的复习文档里，把每道题的代码、思路、复杂度、甚至踩坑记录都汇总在一起，相当于自己的算法错题本。今天这次打卡的内容，也打算一并归档进去。等以后再遇到类似的题，直接翻出来对照，复习效率会高很多。