C++ DFS 与 BFS 算法实战详解

4. 经典例题

例题 1：八皇后（洛谷 P1219）

思路：利用二进制位运算优化状态标记，快速判断列及斜线冲突。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
#define MASK(n) ((1 << (n + 1)) - 2)
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)));
        }
    }
    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）

思路：记录到达每层的最少按钮数 dis[]，若当前步数 k 大于等于已记录的 dis[a]，则剪枝返回。

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

思路：标准的组合型枚举，dfs(u, ind, sum) 分别表示已选数量、起始索引、当前和值。

#include <iostream>
#include <algorithm>
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）

思路：技巧性地给地图外围加障碍（初始化为 1），内部障碍设为 0，避免边界判断。

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

思路：状态压缩 DP 结合 DFS，记录剩余奶酪集合和当前位置。

#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];
double dp[70000][20];
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）

思路：常规 DFS，注意匹配失败时需回溯标记数组。

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 通过队列逐层扩展搜索，保证先访问离起点最近的节点。其核心是'地毯式搜索，层层推进'，适用于无权图的最短路径问题。

2. 特点

• 数据结构：队列。
• 空间复杂度：O(V)（最坏情况存储所有顶点）。
• 时间复杂度：O(V + E)。
• 适用场景：无权图最短路径、层级遍历、广播网络、二分图检测。

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）

思路：马走日有 8 个方向，使用 BFS 层序遍历求最短步长，DFS 会超时。

#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 {
    int x, y, s;
    Node(int _x, int _y, int _s) : x(_x), y(_y), s(_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);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << dis[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

例题 2：迷宫离入口最近的出口（LeetCode 1296）

思路：层序遍历时记录层数，找到边界 '.' 即为最短距离。

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;
}

例题 3：最小基因变化（LeetCode 433）

思路：将字符串变换抽象为图的最短路，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;
}

例题 4：单词接龙（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;
}

例题 5：为高尔夫比赛砍树（LeetCode 675）

思路：按高度排序后，依次计算相邻两棵树间的最短路并累加。

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) {
    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];
    });
    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;
}

5. 多源最短路 BFS

当存在多个起点时，将所有起点同时入队，视为同一层的扩展源。

例题 1：01 矩阵（LeetCode 542）

思路：从所有 0 开始向外扩散，第一次遇到 1 时的层数即为最短距离。

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();
    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 (mat[i][j] == 0) {
                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;
}

例题 2：飞地的数量（LeetCode 1020）

思路：正难则反，从边界上的 1 开始 BFS，标记所有能连到边界的 1，剩下的即为飞地。

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）

思路：01 矩阵变体，从所有水域（0）开始 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）

思路：从所有陆地（1）开始 BFS，找最远的海洋（0）。

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;
}

6. BFS 解决拓扑排序

例题 1：课程表（LeetCode 207）

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

思路：同上，记录出队顺序。

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];
        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）

思路：根据字典序建图，判断是否有环（拓扑排序）。注意处理前缀相同的情况。

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];
            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) {
    for (auto &s : words) {
        for (auto &ch : s) in[ch] = 0;
    }
    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 "";
        }
    }
    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 算法

图像渲染（LeetCode 733）

两种方法均可，DFS 代码更简洁，BFS 避免栈溢出风险。

岛屿数量（LeetCode 200）

遍历矩阵，遇到 '1' 即启动一次搜索（DFS/BFS）标记整个岛屿。

岛屿的最大面积（LeetCode 695）

在搜索过程中统计连通区域大小，取最大值。

四、总结

• DFS 适合探索所有可能性或路径存在性问题，但对最短路径不敏感，需注意递归深度限制。
• BFS 保证无权图最短路径，但内存消耗较大，适合层级相关的问题。
• 实战技巧：组合使用 DFS 和 BFS（如 IDA*），剪枝优化（尤其在 DFS 中），双向 BFS 加速搜索。

使用场景建议：

1. DFS：迷宫探索、图的连通分量、全排列生成、复杂状态转移。
2. BFS：社交网络六度空间、二叉树层次输出、病毒传播模拟、二分图检测。

掌握这两种基础算法，是解决更复杂图论问题的基石。在实际编码中，根据题目对'最短'、'全部'、'层级'的要求灵活选择即可。