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

注意，path 数组不需要在回溯时清零，因为下一次循环会直接覆盖该位置的值；但状态标记数组 st 必须恢复，否则会影响后续分支的判断。

进阶应用：N 皇后问题与剪枝

在搜索过程中，如果当前状态已经不可能满足条件，可以直接停止该分支的搜索，这就是剪枝。以 N 皇后为例，我们需要确保每一行、每一列以及两条对角线上只有一个皇后。

对于对角线判断，数学上可以转化为坐标差值：

• 正对角线：y = x + b => b = y - x（或 x - y），为避免负数索引，可统一加偏移量 n。
• 反对角线：y = -x + b => b = x + y。

通过维护三个布尔数组分别标记列、正对角线和反对角线的占用情况，可以将判断复杂度降为 O(1)。

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

BFS：广度优先搜索

如果说 DFS 是执着地钻牛角尖，那 BFS 就是眼观六路。它从起点开始，先访问所有相邻节点，再依次访问这些节点的邻居，层层推进。BFS 使用队列作为数据结构。

由于它是按层扩展的，因此在无权图中，BFS 第一次到达某个点的路径必然是最短路径。空间复杂度在最坏情况下可能达到 O(2^h)，取决于图的宽度。

迷宫寻路与最短路径

BFS 有一个非常固定的框架：初始化队列，将起点入队，记录距离。每次取出队首元素，将其未访问的邻居入队，并更新距离和前驱节点（用于还原路径）。

#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 q[N * N], Prev[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;
}

树与图的存储及遍历

树本质上是一种特殊的无环图。在实际编程中，我们主要讨论图的存储方式。

图的存储

图分为有向图和无向图。无向图可以看作双向的有向图。存储方式主要有邻接矩阵和邻接表：

• 邻接矩阵：适合稠密图，但空间浪费大，稀疏图不推荐。
• 邻接表：适合稀疏图，节省空间。常用链式前向星（静态链表）实现，效率较高。

链式前向星通过 head, next, to 三个数组模拟链表，无需动态内存分配，运行速度快。

树的遍历

对树或图进行 DFS/BFS 遍历时，核心在于避免重复访问同一个节点。通常需要一个 visited 数组来标记。

树的重心问题示例

求去掉一个根节点后，其子树中最大节点数量的最小值。这需要在 DFS 过程中统计子树大小，并维护全局最小值。

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

const int N = 1e5 + 10;
int n, m, q[N], d[N]; // d 记录每个节点到节点 1 的距离
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;
}

通过上述代码，我们可以看到如何利用静态数组构建邻接表，并结合 BFS 模板求解无权图的最短路径。掌握这些基础模板，是应对更复杂图论问题的关键。