图论算法基础：深入理解 DFS 与 BFS 遍历

#include <iostream>
using namespace std;

const int N = 10;
int n;
char g[N][N];
// 对角线数组需开大一点，防止越界
bool col[N], dg[2 * N], udg[2 * 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)

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

树与图的存储及遍历

图分为有向和无向，稀疏图常用邻接表（链式前向星）存储，比邻接矩阵更节省空间。

无向图中边是双向的，有向图则是单向的。我们通常统一按有向图处理，只需在存无向边时存两次即可。

代码示例

以下演示使用邻接表进行树的宽度优先遍历，计算节点到根的距离。

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