C++ 算法：DFS 与 BFS 详解及经典例题

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 & j];
        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() 函数则用来判断是否为质数。

代码如下：

#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) 进行特殊判断。

代码如下：

#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 吃奶酪 - 洛谷

思路：

• 技巧：状态压缩 DP 结合 DFS。dp[next_t][to] 表示达到当前状态，最后一个吃掉的奶酪编号时的最小距离。

代码如下：

#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）

题目链接：Word Search - LeetCode 79

思路：

• 很常规的 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 <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）

题目链接：Nearest Exit from Entrance in Maze - LeetCode 1926

思路：

• 类似于层序遍历的操作，从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离。

代码如下：

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）

题目链接：Minimum Genetic Mutation - LeetCode 433

思路：

• 如果将「每次字符串的变换」抽象成图中的「两个顶点和一条边」的话，问题就变成了「边权为 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）

题目链接：Word Ladder - LeetCode 127

思路：

• 和上题类似。

代码如下：

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）

题目链接：Cut Off Trees for Golf Event - LeetCode 675

思路：

• 先找出砍树的顺序；
• 然后按照砍树的顺序，一个一个的用 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;
}

6. 多源最短路 BFS

例题 1：01 矩阵（LeetCode 542）

题目链接：01 Matrix - LeetCode 542

对于求的最终结果，我们有两种方式:

• 方法一：从每一个 1 开始，然后通过层序遍历找到离它最近的 0。
• 方法二：从 0 开始层序遍历，并且记录遍历的层数。当第一次碰到 1 的时候，当前的层数就是这个 1 离 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）

题目链接：Number of Enclaves - LeetCode 1020

思路（正难则反）：

• 从边上的 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++;
        }
    }
    return ret;
}

例题 3：地图上的最高点（LeetCode 1765）

题目链接：Map of Highest Peak - LeetCode 1765

思路：

• 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 1162）

题目链接：As Far from Land as Possible - LeetCode 1162

思路：

• 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）

题目链接：Course Schedule - LeetCode 207

思路：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）

题目链接：Course Schedule II - LeetCode 210

思路：和上面类似。

代码如下：

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. 火星词典 - 力扣

思路：将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以用拓扑排序解决。 如何搜集信息 (如何建图)

• 两层 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）

题目链接：Flood Fill - LeetCode 733

思路：

• 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。

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）

题目链接：Number of Islands - LeetCode 200

思路：

• 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。

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 + dir[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）

题目链接：Max Area of Island - LeetCode 695

思路：

• 遍历整个矩阵，每当遇到一块土地的时候，就用「深搜」或者「宽搜」将与这块土地相连的「整个岛屿」的面积计算出来。
• 然后在搜索得到的「所有的岛屿面积」求一个「最大值」即可。在搜索过程中，为了「防止搜到重复的土地」：可以开一个同等规模的「布尔数组」，标记一下这个位置是否已经被访问过;
• 也可以将原始矩阵的 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 + dir[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 加速最短路径搜索

使用场景如下：

1. DFS 适用场景：
   • 路径探索：如迷宫问题、图的连通分量。
   • 回溯问题：如八皇后、全排列。
   • 拓扑排序：通过后序遍历逆序实现。
   • 复杂状态转移：如游戏树搜索（AlphaGo）。
2. BFS 适用场景：
   • 最短路径：如社交网络中的'六度空间'。
   • 层级遍历：如二叉树按层输出。
   • 扩散问题：如病毒传播模拟。
   • 二分图检测：通过交替染色判断。