发布工程信息的网站有哪些_顺义建站公司_优化设计六年级上册数学答案_郑州关键词网站优化排名

在这里插入图片描述

📃个人主页：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 <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
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 <iostream>
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 <iostream>
#include <algorithm>
#include <cstring>
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 <iostream>
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 <iostream>
#include <cmath>
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.

	（-1，-2）		（1，-2）
（-2，-1）				（2，-1）
		（x，y）
（-2，1）				（2，1）
	（-1，2）		（1，2）

这题如果用之前的dfs（step，x，y）来表示则会超时，因此我们应该使用BFS算法层序遍历，遍历每一层，如果遍历了某个节点时，那么后续遍历这个节点绝对比之前找的step要大，层序遍历更适合求最短步长

代码如下：

#include <iostream>
#include <queue>
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 -> bif(!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;
}

三、对比

特性	DFS	BFS
数据结构	栈（递归/非递归）	队列
空间复杂度	𝑂(𝐻)（路径深度）	𝑂(𝑉)（存储所有节点）
最短路径	不保证（可能找到非最短解）	保证（无权图最短路径）
适用场景	路径存在性、回溯问题	最短路径、层级遍历
内存消耗	较低（适合深树）	较高（适合宽图）

经典例题对比 --解决 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适用场景：
- 最短路径：如社交网络中的“六度空间”。
- 层级遍历：如二叉树按层输出。
- 扩散问题：如病毒传播模拟。
- 二分图检测：通过交替染色判断。

在这里插入图片描述