第 11 章：树与图论基础 (Graph Theory Basics)

11.1 图的存储：怎么把图塞进电脑里？

图由点 (Vertex) 和 边 (Edge) 组成。假设我们有 $N$ 个点， $M$ 条边。

11.1.1 邻接矩阵 (Adjacency Matrix)

这是最直观的方法：用一个二维数组 g[N][N]。

g[u][v] = 1 或 w：表示点 $u$ 和点 $v$ 之间有一条边（权重为 $w$ ）。
g[u][v] = 0 或 INF：表示没有边。

int g[1005][1005]; 
// 初始化为无穷大，表示都不通
memset(g, 0x3f, sizeof(g)); 
 
// 添加一条从 u 到 v，权重为 w 的边
g[u][v] = w;
// 如果是无向图（双向通行），还要加反向边
g[v][u] = w;

优点：简单， $O(1)$ 查询两点间有没有边。
缺点：太浪费空间。如果 $N=10^5$ ，开个 int[100000][100000] 的数组直接内存爆炸（MLE）。
适用： $N \le 1000$ 的稠密图。

11.1.2 邻接表 (Adjacency List) —— 竞赛标准写法

我们只记录“存在的边”。用 vector 数组来实现。 vector<int> adj[N]：adj[u] 里存的是所有从 $u$ 出发能到达的点。

// N 个点的图
vector<int> adj[100005]; 
 
// 如果是带权图，可以用 pair 存 {目标点, 权重}
// vector<pair<int, int>> adj[100005];
 
int main() {
    int u, v;
    cin >> u >> v;
    // 添加一条 u -> v 的有向边
    adj[u].push_back(v);
    
    // 如果是无向图
    // adj[v].push_back(u);
}

遍历方法：

// 遍历从 u 出发的所有边
for (int v : adj[u]) {
    // v 是 u 的邻居
}

优点：空间只与边数 $M$ 有关，极度节省空间。
适用：绝大多数图论题目 ( $N, M \le 10^5$ )。

11.2 树 (Tree)：特殊的图

树是一个没有环 (Cycle) 的连通图。它有 $N$ 个点，且恰好有 $N-1$ 条边。

11.2.1 核心概念

根 (Root)：树的顶点（通常规定为 1 号点）。
叶子 (Leaf)：最底下的节点，没有子节点的点（度数为 1）。
深度 (Depth)：根节点深度为 1（或 0），往下逐层 +1。
父与子 (Parent & Child)：相连的两个点，靠近根的是父，远离根的是子。

11.2.2 树的性质

由于树没有环，从点 A 到点 B 的路径只有唯一的一条。这让很多问题变得简单。

LCA (Least Common Ancestor，最近公共祖先)：两个点 $u$ 和 $v$ ，它们向上找祖宗，第一个重合的祖宗就是 LCA。 例如：家族谱系中，你和你表弟的 LCA 是你们的爷爷。
树的直径 (Diameter)：树上最远的两个点之间的距离。

11.3 拓扑排序 (Topological Sort)

这不是给数字排序，而是给任务排序。

场景：你有 4 门课要修：

A：C++ 基础（无前置）
B：数据结构（需先修 A）
C：算法进阶（需先修 B）
D：毕业设计（需先修 C）合理的修课顺序是 $A \to B \to C \to D$ 。这就叫拓扑排序。

如果存在环（A 依赖 B，B 依赖 A），则无法完成拓扑排序。所以它只能用于 DAG (有向无环图)。

11.3.1 Kahn 算法 (基于入度)

入度 (Indegree)：有多少条边指向这个点。
- 如果入度为 0，说明没有任何前置任务，可以直接做。
算法流程：
- 把所有入度为 0 的点扔进队列。
- 每次从队头取出一个点 $u$ （代表任务完成）。
- 把 $u$ 指向的所有邻居 $v$ 的入度减 1（相当于 $u$ 这个前置条件搞定了）。
- 如果 $v$ 的入度变成了 0，说明 $v$ 也可以做了，扔进队列。

代码模板 (必背)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
vector<int> adj[10005];
int in_degree[10005]; // 记录入度
vector<int> result;   // 存储排序结果
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); // u -> v
        in_degree[v]++;      // v 的入度 +1
    }
 
    queue<int> q;
    // 1. 先把所有入度为 0 的点入队
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
 
    // 2. BFS 拆边
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u); // 记录排序顺序
 
        for (int v : adj[u]) {
            in_degree[v]--; // 既然 u 做完了，v 的依赖就少了一个
            if (in_degree[v] == 0) {
                q.push(v); // v 的所有前置都搞定了，入队
            }
        }
    }
 
    // 3. 判断是否有环
    if (result.size() == n) {
        // 输出 result...
    } else {
        cout << "存在环，无法排序" << endl;
    }
    return 0;
}

🧠 本章小结与练习

图论的基础在于建图。只要你会用 vector 存图，你就成功了一半。拓扑排序是解决“依赖问题”的标准解法。

练习作业：

P5318 【深基18.例3】查找文献 (洛谷)：练习图的建立和简单的遍历顺序。
P4017 最大食物链计数：DAG 上的动态规划，需要结合拓扑排序来做。
B3644 【模板】拓扑排序 / 家谱树：直接套用上面的模板。