图论算法入门：DFS 与 BFS 及树图遍历 | 极客日志

C++算法

图论算法入门：DFS 与 BFS 及树图遍历

图论是算法核心，DFS 基于栈实现深度搜索，适合全排列等回溯场景；BFS 基于队列逐层扩展，常用于最短路径问题。本文详解两种遍历原理、剪枝优化、邻接表存储及代码实战，涵盖 N 皇后、迷宫寻路等经典案例，帮助快速掌握图与树的遍历逻辑。

菩提发布于 2026/3/220 浏览

图论算法入门：DFS 与 BFS 及树图遍历

图论是算法领域的基石，而 DFS 和 BFS 则是处理图与树结构最核心的两种遍历策略。

DFS：深度优先搜索

DFS 像一位执着的探索者，它总是沿着一条路径一直走到尽头（叶子节点），然后再回溯去尝试其他分支。从数据结构角度看，DFS 依赖栈来实现递归或显式栈操作。其空间复杂度通常与树的高度成正比，即 O(h)。需要注意的是，由于 DFS 优先深入而非广度扩展，它并不具备直接求解最短路的性质。

全排列问题

这是一个经典的回溯应用场景。我们从第 0 层开始搜索，当搜到第 n 层时说明已经选够了 n 个数，此时输出路径即可。关键在于'恢复现场'：在递归返回后，必须将标记数组 st 重置为未访问状态，以便后续分支能复用该数字。注意 path 数组不需要手动清空，因为下一次循环会直接覆盖旧值。

#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N];

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; i++) printf("%d ", path[i]);
        puts("");
        return;
    }
    for(int i = 1; i <= n; i++){
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            // 恢复现场
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs(0);
    return 0;
}

剪枝操作：N 皇后问题

#include <iostream>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool col[N], dg[N], udg[N]; // 列，正对角线，反对角线

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }
    for(int i = 0; i < n; i++){
        // 检查列和对角线是否冲突
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n + i - u] = true;
            dfs(u + 1);
            // 恢复现场
            g[u][i] = '.';
            col[i] = dg[u + i] = udg[n + i - u] = false;
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) g[i][j] = '.';
    dfs(0);
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e2 + 10;
typedef pair<int, int> PII;
int n, m;
int g[N][N];
int d[N][N]; // 记录距离
PII Prev[N][N]; // 记录前驱
int q[N * N]; // 队列

int bfs(){
    int hh = 0, tt = 0;
    // 队列初始化
    q[0] = {0, 0};
    memset(d, -1, sizeof(d));
    d[0][0] = 0;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    while(hh <= tt){
        auto t = q[hh++];
        for(int i = 0; i < 4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                Prev[x][y] = t; // 记录路径
                q[++tt] = {x, y};
            }
        }
    }
    return d[n - 1][m - 1];
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> g[i][j];
    cout << bfs();
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m, q[N], d[N];
int e[N], h[N], idx, ne[N];

// 添加边
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs(){
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs();
    return 0;
}