【C++ 算法】DFS & BFS 一篇速成学习_c++ dfs bfs 知乎
📃个人主页：island1314
⛺️ 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
- 生活总是不会一帆风顺，前进的道路也不会永远一马平川，如何面对挫折影响人生走向 – 《人民日报》
🔥 目录
-
- 一、DFS
-
- 1. 基本思想
- 2. 特点
- 3. C++实现
- 4. 经典例题
-
- 例题1：八皇后（洛谷P1219）
- 例题2：奇怪的电梯（洛谷P1135）
- 例题3：选数（洛谷P1036）
- 例题4：迷宫（洛谷P1605）
- 例题5：吃奶酪（洛谷P1433）
- 例题6：单词搜索（LeetCode 79）
- 二、BFS
-
- 1. 基本思想
- 2. 特点
- 3. C++实现
- 4. 经典例题
-
- 例题1：马的遍历（洛谷P1443）
- 5. BFS 解决最短路问题
-
- 例题1：迷宫离入口最近的出口（LeetCode 1296）
- 例题2：最小基因变化（LeetCode 433）
- 例题3：单词接龙（LeetCode 127）
- 例题4：为高尔夫比赛砍树（LeetCode 675）
- 6. 多源最短路 BFS
-
- 例题1：01 矩阵（LeetCode 542）
- 例题2：飞地的数量（LeetCode 1020）
- 例题3：地图上的最高点（LeetCode 1765）
- 例题4：地图分析（LeetCode 1765）
- 8. BFS 解决拓扑排序
-
- 例题1：课程表（LeetCode 207）
- 例题2：课程表II（LeetCode 210）
- 例题3：火星词典（LeetCode LCR 114）
- 三、对比
-
- 经典例题对比 --解决 FloodFill 算法
-
- 例题1：图像渲染（LeetCode 733）
- 例题2：岛屿数量（LeetCode 200）
- 例题3：岛屿的最大面积（LeetCode 695）
- 四、总结
一、DFS
1. 基本思想
DFS（Depth-First Search）是一种通过递归或显式栈结构实现的搜索算法，其核心思想是 “一条路走到黑，不撞南墙不回头”。它会沿着某条分支尽可能深入，直到无法继续时回溯到上一个分叉点
2. 特点
- 数据结构：使用栈（递归调用栈或手动维护的栈）。
- 空间复杂度：取决于递归深度，最坏为 𝑂(𝐻)O(H)（𝐻H 为树的高度或图的深度）。
- 时间复杂度：𝑂(𝑉+𝐸)O(V+E)（遍历所有顶点和边）。
- 适用场景：
- 路径搜索（如迷宫问题）
- 连通性检测（如岛屿问题）
- 回溯问题（如排列组合、N皇后）
- 拓扑排序（后序遍历逆序）
3. C++实现
-
递归实现（以图的遍历为例）
void dfs(int u, vector<bool>& visited, vector<vector<int>>& graph) { visited[u] = true; for (int v : graph[u]) { if (!visited[v]) { dfs(v, visited, graph); } }} -
非递归实现（显式栈）
void dfs_iterative(int start, vector<vector<int>>& graph) { stack<int> st; vector<bool> visited(graph.size(), false); st.push(start); visited[start] = true; while (!st.empty()) { int u = st.top(); st.pop(); for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; st.push(v); } } }}
4. 经典例题
例题1：八皇后（洛谷P1219）
题目链接：USACO1.5 八皇后 Checker Challenge - 洛谷
思路：二进制来表示
代码如下：
#include #include #include #include #include using namespace std;int n;#define MASK(n) ((1<<(n+1))-2) //如 6 得到的是1000 0000 -> 111 1110,零位上的1不用unordered_map<int, int> ind;int tot = 3;int arr[20];void out(){for (int i = 1; i <= n; i++) {if (i > 1) cout << \" \";printf(\"%d\", arr[i]);}printf(\"\\n\");tot--;return;}int dfs(int i, int t1, int t2, int t3) {if (i > n) {if(tot) out();return 1;}int ans = 0;for (int t = t1; t; t -= (-t & t)) {int j = ind[-t & t];if ((t2 & (1 << (i + j - 1))) && (t3 & (1 << (i - j + n)))) //正斜线和反斜线{arr[i] = j;ans += dfs(i + 1, t1^(1 << j), t2^(1 << (i + j - 1)), t3^(1 << (i - j + n))); //把t1中的j标记为0,然后向左移动一位}}return ans;}int main(){scanf(\"%d\", &n);for (int i = 0; i < 2 * n; i++) ind[1 << i] = i;int ans = dfs(1, MASK(n), MASK(2 * n - 1), MASK(2 * n - 1)); //列，正斜边，反斜边cout << ans << \"\\n\";return 0;}例题2：奇怪的电梯（洛谷P1135）
题目链接：P1135 奇怪的电梯 - 洛谷
思路：
- 先设立两个数组dis[]和to[]，分别**表示到某层的最少按钮数和按键，dfs(k , a)中k表示使用的按钮数目，a表示到某一层，**当dis[]记录到的到某层的最少按钮数小于等于k时，就可递归返回。
代码如下：
#include using namespace std;const int N = 205;int to[N], dis[N]; //起点到每个点最短距离int n;void dfs(int k, int a){if (dis[a] <= k) return;dis[a] = k; //刷新到a的最短距离if (a + to[a] <= n) dfs(k + 1, a + to[a]);if (a - to[a] >= 1) dfs(k + 1, a - to[a]);}int main(){int a, b;cin >> n >> a >> b;for (int i = 1; i <= n; i++) {cin >> to[i]; //输入每个按钮的值dis[i] = n + 1;}dfs(0, a);printf(\"%d\\n\", dis[b] == n + 1 ? -1 : dis[b]);return 0;}例题3：选数（洛谷P1036）
题目链接：P1036 NOIP 2002 普及组选数 - 洛谷
思路：
- **dfs(u, ind, sum)**分别表示当前已经选择了几个数，当前这一层可以选择的最小数字，所选当前的和值，is_prime()函数则用来判断是否为质数。
- 这题与之前文章里的【题目/算法训练】全排列相关问题（不用next-permutation）中的组合型枚举很像，想了解的朋友们可以下
代码如下：
#include #include #include using namespace std;const int N = 25;int a[N];int n, k;long long ans = 0; //计算素数的数量bool is_prime(int x){if (x < 2) return false;for (int i = 2; i <= x / i; i++){if (x % i == 0) return false;}return true;}void dfs(int u,int ind, int sum){if (u == k) {if (is_prime(sum)) ans++;return;}for(int i = ind; i <= n; i++){dfs(u + 1, i + 1,sum + a[i]);}}int main(){cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];dfs(0, 1, 0); printf(\"%lld\\n\", ans);return 0;}例题4：迷宫（洛谷P1605）
题目链接：P1605 迷宫 - 洛谷
思路：
- **技巧：**从（1，1）开始读入，给地图上可以行走的地方初始化为1，0表示不可以走的点，相当于给地图外面放上障碍，就不用向上面一样对(x，y)进行特殊判断（如判断是否为1该点相邻的点，是不是障碍，有没有访问过）
代码如下：
#include using namespace std;const int N = 7;int g[N][N];int n, m, t, sx, sy, ex, ey;int ans = 0; //记录方法的数量int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};void dfs(int x, int y){if (x == ex && y == ey) {ans++;return;}g[x][y] = 0;//表示当前点遍历过for (int i = 0; i < 4; i++) {int dx = x + dir[i][0], dy = y + dir[i][1];if (g[dx][dy] == 0) continue;dfs(dx, dy);}g[x][y] = 1;}int main(){cin >> n >> m >> t;for (int i = 1; i <= n; i++){for(int j =1;j<=m;j++) g[i][j] = 1;}cin >> sx >> sy >> ex >> ey;for (int i = 0; i < t; i++) {int x, y;cin >> x >> y;g[x][y] = 0;}dfs(sx, sy);cout << ans << \"\\n\";return 0;}例题5：吃奶酪（洛谷P1433）
题目链接：P1433 吃奶酪 - 洛谷
思路：
- **技巧：**从（1，1）开始读入，给地图上可以行走的地方初始化为1，0表示不可以走的点，相当于给地图外面放上障碍，就不用向上面一样对(x，y)进行特殊判断（如判断是否为1该点相邻的点，是不是障碍，有没有访问过）
代码如下：
#include #include using namespace std;const int N = 17;double ans = 1e9;int n;double x[N], y[N];double dis[N][N]; //dis[i][j]表示从第i个奶酪到第j个奶酪的距离double dp[70000][20]; //2^16,第一个位置表示状态编码,第二个位置表示达到当前状态，最后一个吃掉的奶酪编号int ind[70000]; //权值映射double d(int i, int j) {return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])* (y[i] - y[j]));}void dfs(int t, int now, double s) {if (t == 0) { //吃掉了所有奶酪if (s < ans) ans = s;return;}for (int k = t; k; k -= (k & -k)) {int to = ind[k & -k], next_t = t - (1 << to);double l = s + dis[now][to];if (dp[next_t][to] != 0 && dp[next_t][to] <= l) continue;dp[next_t][to] = l;if (ans <= l) continue;dfs(next_t, to, l);}}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;x[0] = y[0] = 0; //小老鼠位置for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];for (int i = 0; i <= n; i++){for (int j = i; j <= n; j++) dis[i][j] = dis[j][i] = d(i, j);}for (int k = 1, i = 0; i <= N; i++, k *= 2)ind[k] = i; //权值到下标映射dfs((1 << (n + 1)) - 2, 0, 0); //当前位置状态码，所在奶酪下标，到达状态所走总路程printf(\"%.2lf\\n\", ans);return 0;}例题6：单词搜索（LeetCode 79）
题目链接：P1433 吃奶酪 - 洛谷
思路：
- 很常规的DFS搜索，当第一个字符发生匹配时，就开始往下搜索，不匹配就退回来，直到遍历完所有字符都没有匹配成功，才返回false.
- 因此需要注意的是：应该是写成
if (dfs(board, word, i, j, 0)) return true;，而不是return dfs(board, word, i, j, 0);
代码如下：
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int n, m;bool st[505][505];bool dfs(vector<vector<char>>& board, string word, int x, int y, int pos) { if (pos == word.size()) return true; // 向量的方式，定义上下左右四个位置 for (int i = 0; i < 4; i++) { int dx = x + dir[i][0], dy = y + dir[i][1]; if (dx >= 0 && dx < n && dy >= 0 && dy < m && board[dx][dy] == word[pos] && !st[dx][dy]) { st[dx][dy] = true; if (dfs(board, word, dx, dy, pos + 1)) return true; st[dx][dy] = false; } } return false;}bool exist(vector<vector<char>>& board, string word) { n = board.size(), m = board[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == word[0]) { st[i][j] = true; if (dfs(board, word, i, j, 1)) return true; st[i][j] = false; } } } return false;}二、BFS
1. 基本思想
BFS（Breadth-First Search）通过队列逐层扩展搜索，保证先访问离起点最近的节点。其核心是“地毯式搜索，层层推进”。
2. 特点
- 数据结构：使用队列。
- 空间复杂度：𝑂(𝑉)O(V)（最坏情况存储所有顶点）。
- 时间复杂度：𝑂(𝑉+𝐸)O(V+E)。
- 适用场景：
- 无权图的最短路径（如迷宫最短步数）。
- 层级遍历（如二叉树的层次遍历）。
- 广播网络（如社交网络中的信息扩散）。
- 检测图的二分性（Bipartite）
3. C++实现
-
标准实现（以图的遍历为例）
void bfs(int start, vector<vector<int>>& graph) { queue<int> q; vector<bool> visited(graph.size(), false); q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }}
4. 经典例题
例题1：马的遍历（洛谷P1443）
题目链接：P1443 马的遍历 - 洛谷
思路：
- 假设马在（x，y）这个点，则马可以移动的方向有8个，偏移量如下所示，注意马走日。
- 注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 ∣x1−x∣+∣y1−y∣=3.
这题如果用之前的dfs（step，x，y）来表示则会超时，因此我们应该使用BFS算法层序遍历，遍历每一层，如果遍历了某个节点时，那么后续遍历这个节点绝对比之前找的step要大，层序遍历更适合求最短步长
代码如下：
#include #include using namespace std;const int N = 405;int dir[8][2] = { //偏移量{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{1,-2}, {-1,2},{-1,-2}};int dis[N][N];int n, m;struct Node { //广搜队列Node(int x, int y, int s) :x(x), y(y), s(s) {}int x, y, s;};void bfs(int a, int b){queue<Node> q;q.push(Node(a, b, 0));dis[a][b] = 0;//从当前节点扩展到其他点while (!q.empty()) {Node now = q.front();q.pop();for (int k = 0; k < 8; k++) {int dx = now.x + dir[k][0], dy = now.y + dir[k][1];if (dx < 1 || dx > n) continue;if (dy < 1 || dy > m) continue;if (dis[dx][dy] != -1)continue;q.push(Node(dx, dy, now.s + 1));dis[dx][dy] = now.s + 1;}}}int main(){int a, b;cin >> n >> m >> a >> b;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dis[i][j] = -1; //赋初值}}bfs(a, b); //到达当前点所花步数，(a,b)表示当前所在位置for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << dis[i][j] << \" \";}cout << \"\\n\";}return 0;}5. BFS 解决最短路问题
例题1：迷宫离入口最近的出口（LeetCode 1296）
题目链接：1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
思路：
- 类似于层序遍历的操作，从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离。
代码如下
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { int n = maze.size(), m = maze[0].size(); queue<pair<int, int>> q; q.push({entrance[0], entrance[1]}); vector<vector<int>> vis(n, vector<int>(m)); vis[entrance[0]][entrance[1]] = true; int ans = 0; while (!q.empty()) { ans++; int size = q.size(); while (size--) { auto [x, y] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int dx = x + dir[k][0], dy = y + dir[k][1]; if (dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && maze[dx][dy] == \'.\') { if (dx == 0 || dx == n - 1 || dy == 0 || dy == m - 1) return ans; q.push({dx, dy}); vis[dx][dy] = true; } } } } return -1;}例题2：最小基因变化（LeetCode 433）
题目链接：433. 最小基因变化 - 力扣（LeetCode）
思路：
- 如果将「每次字符串的变换」抽象成图中的「两个顶点和一条边」的话，问题就变成了「边权为 1的最短路问题」
- 因此，从起始的字符串开始，来一次 bfs即可
代码如下
int minMutation(string startGene, string endGene, vector<string>& bank) { unordered_set<string> vis; unordered_set<string> hash(bank.begin(), bank.end()); if(startGene == endGene) return 0; if(!hash.count(endGene)) return -1; string change = \"ACGT\"; queue<string> q; q.push(startGene); vis.insert(startGene); int ret = 0; while(!q.empty()){ ret++; int size = q.size(); while(size--){ string t = q.front(); q.pop(); for(int i = 0; i < 8; i++){ string tmp = t; for(int j = 0; j <change.size(); j++){ tmp[i] = change[j]; if(hash.count(tmp) && !vis.count(tmp)){ if(tmp == endGene) return ret; q.push(tmp); vis.insert(tmp); } } } } } return -1;}例题3：单词接龙（LeetCode 127）
题目链接：127. 单词接龙 - 力扣（LeetCode）
思路：
- 和上题类似
代码如下
int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> hash(wordList.begin(), wordList.end()); unordered_set<string> vis; if(hash.count(endWord) == 0) return 0; queue<string> q; q.push(beginWord); vis.insert(beginWord); int ret = 1; while(!q.empty()){ ret++; int size = q.size(); while(size--){ string t = q.front(); q.pop(); for(int i = 0; i < t.size(); i++){ string tmp = t; for(char ch = \'a\'; ch <= \'z\'; ch++){ tmp[i] = ch; if(hash.count(tmp) && !vis.count(tmp)){ if(tmp == endWord) return ret; q.push(tmp); vis.insert(tmp); } } } } } return 0;}例题4：为高尔夫比赛砍树（LeetCode 675）
题目链接：675. 为高尔夫比赛砍树 - 力扣（LeetCode）
- 先找出砍树的顺序;
- 然后按照砍树的顺序，一个一个的用 bfs 求出最短路即可。
代码如下
int m, n;bool vis[55][55];int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};int bfs(vector<vector<int>> &forest, int bx, int by, int ex, int ey){ if(bx == ex && by == ey) return 0; queue<pair<int, int>> q; memset(vis, 0, sizeof(vis)); q.push({bx, by}); vis[bx][by] = true; int step = 0; while(!q.empty()){ step++; int size = q.size(); while(size--){ auto[a, b] = q.front(); q.pop(); for(int i = 0; i < 4; i++){ int x = a + dir[i][0], y = b + dir[i][1]; if(x >= 0 && x < n && y >= 0 && y < m && forest[x][y] && !vis[x][y]){ if(x == ex && y == ey) return step; q.push({x, y}); vis[x][y] = true; } } } } return -1;}int cutOffTree(vector<vector<int>>& forest) { // 1. 找出砍树顺序(从小到大) n = forest.size(), m = forest[0].size(); vector<pair<int, int>> trees; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(forest[i][j] > 1){ trees.push_back({i, j}); } } } sort(trees.begin(), trees.end(), [&](const pair<int, int> x, const pair<int, int> y){ return forest[x.first][x.second] < forest[y.first][y.second]; }); // 2. 按照顺序砍树 -- 相邻树的最短距离 int bx = 0, by = 0; int ret = 0; for(auto &[a, b]: trees){ int step = bfs(forest, bx, by, a, b); if(step == -1) return -1; ret += step; bx = a, by = b; } return ret;}https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/6. 多源最短路 BFS
例题1：01 矩阵（LeetCode 542）
题目链接：542. 01 矩阵 - 力扣（LeetCode）
对于求的最终结果，我们有两种方式:
- 方法一：从每一个 1 开始，然后通过层序遍历找到离它最近的0。
- 这一种方式，我们会以所有的 1起点，来一次层序遍历，势必会遍历到很多重复的点。并且如果矩阵中只有一个 0的话，每一次层序遍历都要遍历很多层，时间复杂度较高。
- 方法二：从 0 开始层序遍历，并且记录遍历的层数。当第一次碰到 1 的时候，当前的层数就是这个 1离 0 的最短距离
- 这一种方式，我们在遍历的时候标记一下处理过的1，能够做到只用遍历整个矩阵一次，就能得到最终结果。
- 但是，这里有一个问题，0是有很多个的，我们怎么才能保证遇到的1距离这一个 0是最近的呢?
- 其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。
代码如下
int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int n = mat.size(), m = mat[0].size(); // dist[i][j] == -1 没有搜索过 vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; // 1. 把所有点放入队列 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(mat[i][j] == 0) { dist[i][j] = 0; q.push({i, j}); } } } // 2. 一层一层扩展 while(!q.empty()){ auto [a, b] = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int x = a + dir[k][0], y = b + dir[k][1]; if(x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1){ dist[x][y] = dist[a][b] + 1; q.push({x, y}); } } } return dist; }例题2：飞地的数量（LeetCode 1020）
题目链接：1020. 飞地的数量 - 力扣（LeetCode）
思路（正难则反）
- 从边上的 1开始搜索，把与边上1相连的联通区域全部标记一下然后再遍历一遍矩阵，看看哪些位置的1没有被标记即可标记的时候，可以用「多源 bfs 」解决。
代码如下
int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};int numEnclaves(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(); vector<vector<bool>> vis(n, vector<bool>(m)); queue<pair<int, int>> q; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if((i == 0 || i == n - 1 || j == 0 || j == m - 1) && grid[i][j] == 1) { q.push({i, j}); vis[i][j] = true; } } } while(!q.empty()){ auto [a, b] = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int x = a + dir[k][0], y = b + dir[k][1]; if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid[x][y] == 1){ q.push({x, y}); vis[x][y] = true; } } } int ret = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == 1 && !vis[i][j]) ret++; } }例题3：地图上的最高点（LeetCode 1765）
题目链接：1765. 地图中的最高点 - 力扣（LeetCode）
思路
- 01 矩阵的变型题，直接用多源 BFS 解决
代码如下
int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};vector<vector<int>> highestPeak(vector<vector<int>>& isWater) { int n = isWater.size(), m = isWater[0].size(); vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(isWater[i][j]){ dist[i][j] = 0; q.push({i, j}); } } } while(!q.empty()) { auto [a, b] = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int x = a + dir[k][0], y = b + dir[k][1]; if(x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1 ){ dist[x][y] = dist[a][b] + 1; q.push({x, y}); } } } return dist;}例题4：地图分析（LeetCode 1765）
题目链接：1162. 地图分析 - 力扣（LeetCode）
思路
- 01 矩阵的变体
代码如下
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int maxDistance(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j]) { // 所有陆地 dist[i][j] = 0; q.push({i, j}); } } } int ret = -1; while (!q.empty()) { auto [a, b] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int x = a + dir[k][0], y = b + dir[k][1]; if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1) { dist[x][y] = dist[a][b] + 1; q.push({x, y}); ret = max(ret, dist[x][y]); } } } return ret;}8. BFS 解决拓扑排序
例题1：课程表（LeetCode 207）
题目链接：207. 课程表 - 力扣（LeetCode）
思路：BFS 解决拓扑排序即可
- 将所有入度为0的点加入到队列中;当队列不空的时候，一直循环:
- 取出队头元素;
- 将于队头元素相连的顶点的入度-1;
- 然后判断是否减成 0,。如果减成0，就加入到队列中。
代码如下
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); vector<int> d(numCourses, 0); queue<int> q; for(auto e: prerequisites){ int u = e[0], v = e[1]; adj[u].emplace_back(v); d[v]++; } for(int i = 0; i < numCourses; i++){ if(d[i] == 0) q.push(i); } int cnt = 0; while(!q.empty()){ int u = q.front(); q.pop(); cnt++; for(auto v: adj[u]){ if(--d[v] == 0) q.push(v); } } return cnt == numCourses;}例题2：课程表II（LeetCode 210）
题目链接：210. 课程表 II - 力扣（LeetCode）
思路：和上面类似
代码如下
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); vector<int> d(numCourses, 0); for(auto e: prerequisites){ int v = e[0], u = e[1]; // e[0] <- e[1] adj[u].push_back(v); d[v]++; } queue<int> q; for(int i = 0; i < numCourses; i++){ if(d[i] == 0) q.push(i); } vector<int> ans; while(!q.empty()){ int u = q.front(); q.pop(); ans.push_back(u); for(auto v: adj[u]){ if(--d[v] == 0) q.push(v); } } return ans.size() != numCourses ? vector<int>() : ans;}例题3：火星词典（LeetCode LCR 114）
题目链接：LCR 114. 火星词典 - 力扣（LeetCode）
思路：将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以用拓扑排序解决。
如何搜集信息(如何建图)
- 两层 for 循环枚举出所有的两个字符串的组合;
- 然后利用指针，根据字典序规则找出信息。
代码如下
unordered_map<char, unordered_set<char>> edges;unordered_map<char, int> in; // 入度bool add(string &s1, string &s2){ int n = min(s1.size(), s2.size()); int i = 0; for(; i < n; i++){ if(s1[i] != s2[i]){ char a = s1[i], b = s2[i]; // a -> b if(!edges.count(a) || !edges[a].count(b)){ edges[a].insert(b); in[b]++; } break; } } if(i == s2.size() && i < s1.size()) return true; return false;}string alienOrder(vector<string>& words) { // 1. 建图 + 初始化入度 for(auto &s: words){ for(auto &ch: s){ in[ch] = 0; } } // 2. 连接 int n = words.size(); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(add(words[i], words[j])) return \"\"; } } // 3. 拓扑排序 queue<char> q; for(auto &[a, b]: in){ if(b == 0) q.push(a); } string ret; while(!q.empty()){ char t = q.front(); q.pop(); ret += t; for(auto ch: edges[t]){ if(--in[ch] == 0) q.push(ch); } } for(auto &[a, b]: in){ if(b != 0) return \"\"; } return ret;}三、对比
经典例题对比 --解决 FloodFill 算法
例题1：图像渲染（LeetCode 733）
题目链接：733. 图像渲染 - 力扣（LeetCode）
思路：
- 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可
DFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};typedef pair<int, int> PII;vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int target = image[sr][sc]; if (target == color) return image; int m = image.size(), n = image[0].size(); queue<PII> q; q.push({sr, sc}); while(!q.empty()){ auto [a, b] = q.front(); q.pop(); image[a][b] = color; for(int i = 0; i < 4; i++){ int x = a + dir[i][0], y = b + dir[i][1]; if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target){ q.push({x, y}); } } } return image;}BFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};typedef pair<int, int> PII;vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int target = image[sr][sc]; if (target == color) return image; int m = image.size(), n = image[0].size(); queue<PII> q; q.push({sr, sc}); while(!q.empty()){ auto [a, b] = q.front(); q.pop(); image[a][b] = color; for(int i = 0; i < 4; i++){ int x = a + dir[i][0], y = b + dir[i][1]; if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target){ q.push({x, y}); } } } return image;}例题2：岛屿数量（LeetCode 200）
题目链接：200. 岛屿数量 - 力扣（LeetCode）
思路：
- 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可
DFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};int n, m;bool vis[505][505]; //标记该点是否用过void dfs(vector<vector<char>>& grid, int x, int y){ vis[x][y] = true; for (int i = 0; i < 4; i++) { int dx = x + dir[i][0], dy = y + dir[i][1]; if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == \'1\') { dfs(grid, dx, dy); } }}int numIslands(vector<vector<char>>& grid) { m = grid.size(), n = grid[0].size(); int ret = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++){ if (!vis[i][j] && grid[i][j] == \'1\') { ret++; dfs(grid, i, j); } } } return ret;}BFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};bool vis[305][305];int m, n;void bfs(vector<vector<char>>& grid, int i, int j){ queue<pair<int, int>> q; q.push({ i, j }); vis[i][j] = true; while (q.size()){ auto [a, b] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int x = a + dir[k][0], y = b + dy[k][1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == \'1\' &&!vis[x][y]) { q.push({ x, y }); vis[x][y] = true; } } }}int numIslands(vector<vector<char>>& grid){ m = grid.size(), n = grid[0].size(); int ret = 0; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ if (grid[i][j] == \'1\' && !vis[i][j]){ ret++; bfs(grid, i, j); // 把这块陆地全部标记⼀下 } } } return ret;}例题3：岛屿的最大面积（LeetCode 695）
题目链接：695. 岛屿的最大面积 - 力扣（LeetCode）
思路：
- 遍历整个矩阵，每当遇到一块土地的时候，就用「深搜」或者「宽搜」将与这块土地相连的「整个岛屿」的面积计算出来。
- 然后在搜索得到的「所有的岛屿面积」求一个「最大值」即可。在搜索过程中，为了「防止搜到重复的土地」：可以开一个同等规模的「布尔数组」，标记一下这个位置是否已经被访问过;。
- 也可以将原始矩阵的 1修改成 0，但是这样操作会修改原始矩阵
DFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};int n, m, cnt;bool vis[505][505]; //标记该点是否用过void dfs(vector<vector<int>>& grid, int x, int y){ vis[x][y] = true; cnt++; //记录每块岛屿的面积 for (int i = 0; i < 4; i++) { int dx = x + dir[i][0], dy = y + dir[i][1]; if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && grid[dx][dy] == 1) { dfs(grid, dx, dy); } }}int maxAreaOfIsland(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); int ret = 0; //统计最大数量 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!vis[i][j] && grid[i][j] == 1) { cnt = 0; dfs(grid, i, j); ret = max(cnt, ret); } } } return ret;}BFS 方法如下：
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1}};bool vis[51][51];int m, n;int bfs(vector<vector<int>>& grid, int i, int j){ int count = 0; queue<pair<int, int>> q; q.push({ i, j }); vis[i][j] = true; count++; while (q.size()) { auto [a, b] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int x = a + dir[k][0], y = b + dy[k][1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) { q.push({ x, y }); vis[x][y] = true; count++; } } } return count;}int maxAreaOfIsland(vector<vector<int>>& grid){ m = grid.size(), n = grid[0].size(); int ret = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1 && !vis[i][j]) { ret = max(ret, bfs(grid, i, j)); } } } return ret;}四、总结
- DFS 以深度优先，适合探索所有可能性或路径存在性问题，但对最短路径不敏感。
- BFS 以广度优先，保证最短路径，但内存消耗较大。
- 实战技巧：
- 组合使用DFS和BFS（如IDA*算法）。
- 剪枝优化（尤其在DFS中减少无效搜索）。
- 双向BFS加速最短路径搜索
使用场景如下：
- DFS适用场景：
- 路径探索：如迷宫问题、图的连通分量。
- 回溯问题：如八皇后、全排列。
- 拓扑排序：通过后序遍历逆序实现。
- 复杂状态转移：如游戏树搜索（AlphaGo）。
- BFS适用场景：
- 最短路径：如社交网络中的“六度空间”。
- 层级遍历：如二叉树按层输出。
- 扩散问题：如病毒传播模拟。
- 二分图检测：通过交替染色判断。
