信息学奥赛图论入门：图、DFS、BFS 与最短路

电脑怎么存一张图？两种方式：

邻接矩阵：用一个二维数组 g[i][j] 表示 i 和 j 之间有没有边。优点是判断两点间有没有边只要 O(1)；缺点是 n 个点要开 n 的平方个空间，n=10000 时内存不够。

邻接表：用一个 vector 数组，g[i] 存着 i 所有邻居的列表。n=10000 只有边数个空间，竞赛里最常用。

#include <vector>
using namespace std;

vector<int> g[100005];   // 邻接表

void addEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);   // 无向图要加两次
}

入门阶段先掌握邻接表，邻接矩阵只在 n 很小（n≤500）时用。

DFS（Depth-First Search）的思路：从起点出发，选一个邻居走过去，再选那个点的一个邻居继续走，直到走不动了就回头换路。就像走迷宫，沿着一条路一直走到死胡同，再退回来走另一条。

bool visited[100005];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : g[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// 调用: dfs(1);

关键是 visited 数组，标记哪些点已经走过，防止无限循环。DFS 适合判断连通性（两个点在不在一起）、判断有没有环。

BFS（Breadth-First Search）的思路：从起点开始，先访问所有距离 1 的点，再访问距离 2 的，再访问距离 3 的……一圈一圈向外扩散。就像往水里扔石头，波纹一圈圈扩大。

#include <queue>

int dist[100005];
bool visited[100005];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

BFS 用队列实现。它的核心优势是：在无权图上，BFS 第一次访问到某个点时，走的就是最短路径。

"无权图"就是每条边长度都是 1。这种图上，从起点到终点最少要走几步？BFS 天然解决这个问题——dist[v] 存的就是起点到 v 的最短步数。

举个例子：迷宫里从左上角走到右下角，每步可以上下左右走一格，最少几步？把每个格子看成一个点，相邻格子之间连边，跑一次 BFS，dist[终点] 就是答案。

如果边有权重（公路长度不同），BFS 就不够用了，要用 Dijkstra 算法。那是图论进阶内容，入门阶段先把无权图 BFS 练熟。