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

剪枝操作：N 皇后问题

在 DFS 基础上加入剪枝可以大幅减少无效搜索。以 N 皇后为例，我们需要确保任意两个皇后不在同一行、同一列或同一对角线上。

• 列冲突：用 col[i] 记录第 i 列是否被占用。
• 主对角线：y = x + b，即 b = y - x。为避免负数索引，通常偏移一个常数，如 x - y + n。
• 副对角线：y = -x + b，即 b = x + y。

通过枚举每一行的放置位置，利用上述三个布尔数组快速判断合法性。

#include <iostream>
using namespace std;

const int N = 15; // 适当扩大范围以防越界
int n;
char g[N][N];
bool col[N], dg[N * 2], udg[N * 2]; // 对角线数组需足够大

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 - u + i] = true;
            dfs(u + 1);
            // 回溯
            g[u][i] = '.';
            col[i] = dg[u + i] = udg[n - u + i] = 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)

BFS 则像一位视野开阔的搜索者，它一层一层地向外扩展，每次只关注当前距离最近的点。从数据结构看，BFS 依赖队列实现。

BFS 的空间复杂度通常为 O(2^h)，因为它需要存储当前层的所有节点。由于它是按层搜索的，BFS 天然具备寻找无权图最短路性质的特点。

迷宫寻路与最短路

宽搜有一个相对固定的框架：初始化队列，入队起点，然后不断取出队首元素，将其相邻且未访问的点入队。为了还原路径，可以使用 Prev 数组记录每个点的前驱节点。

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

const int N = 105;
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];
            int 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() << endl;
    return 0;
}

树与图的存储及遍历

树是一种特殊的无环图。在实际编程中，我们通常统一讨论图的存储和遍历。

图的存储方式

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

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

邻接表的核心在于每个节点维护一个单链表，指向其所有邻居节点。

树的 DFS 遍历

我们可以利用 DFS 遍历树结构，计算以每个节点为根的子树大小，进而求解最大子树节点数等问题。这通常涉及全局变量更新和递归回溯。

图的 BFS 遍历

对于无权图的最短路径问题，BFS 是首选。以下示例展示了如何使用邻接表构建图并进行 BFS 求节点 1 到节点 n 的最短距离。

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

// 添加边 a -> b
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() << endl;
    return 0;
}

掌握这两种遍历方式是解决图论问题的基石。实际应用中，根据问题特性选择 DFS 或 BFS，配合合适的存储结构，往往能事半功倍。