算法讲解059 必备 建图、链式前向星、拓扑排序

来源：算法讲解059【必备】建图、链式前向星、拓扑排序　·　2026-10-25

依据：视频字幕 2000 字

一句话概括

用三种方式（邻接矩阵、邻接表、链式前向星）把图存进计算机，再用拓扑排序（Topological Sort）对有向无环图（DAG）求出一个线性顺序。

它解决什么问题

• 输入给一堆「点 u 到点 v 有一条边（可能带权 w）」，需要把图存下来供后续算法使用。
• 需要判断一个有向图有没有环，或者求一个满足「所有边都从前指向后」的顶点排列（任务调度、依赖关系、课程安排）。
• 链式前向星解决的是：点数/边数到 1e6 级别时，vector<vector<int>> 的堆分配和指针跳转太慢、list/map 更不能用，需要一块连续静态数组把边存下来。

基础知识（前置概念，用大白话解释）

• 图（Graph）：点集 V 和边集 E。边有方向叫「有向图（Directed Graph）」，没方向叫「无向图（Undirected Graph）」。
• 带权图（Weighted Graph）：每条边附带一个数值（距离、花费）。
• 入度（In-degree）：有多少条边指向这个点。出度（Out-degree）反之。
• DAG（Directed Acyclic Graph，有向无环图）：有向但没有环的图。拓扑排序只对 DAG 存在。
• 队列（Queue）：先进先出。拓扑排序的 Kahn 算法靠它驱动；用数组 + 两个下标 head/tail 手写，比 std::queue 常数小。
• 静态数组建图：所有边预先开在一个大数组里，用下标当「指针」，避免动态分配。

原理（为什么这么做是对的，尽量给直觉）

三种建图方式的直觉：

• 邻接矩阵：g[u][v] 直接查，O(1) 判边，但空间 O(n²)，n 上万就爆。
• 邻接表：每个点挂一个出边列表，空间 O(n+m)，遍历某点的出边很快。
• 链式前向星：本质就是「用数组模拟邻接表」。每个点存一个 head[u]（第一条出边的下标），每条边存 next[i]（同起点的下一条边的下标）。遍历时 for (int i = head[u]; i != -1; i = nxt[i])，效果和邻接表一样，但全部落在连续内存里，cache 友好、无堆分配。

拓扑排序为什么对（Kahn 算法）：

DAG 里一定存在入度为 0 的点（否则沿着入边一直往回走必然成环）。把入度为 0 的点拿出来放进答案，然后「删掉」它的所有出边——等价于把它指向的点的入度减 1。减到 0 的点说明它所有前驱都已经排进答案了，可以安全入队。反复做，直到队列空。

• 如果最终排进答案的点数 == n，说明是 DAG，排序成功。
• 如果 < n，说明剩下的点互相卡着入度不为 0，即存在环。

直觉：每次取「当前没有任何未完成前置任务」的任务，这是唯一合法的执行顺序来源。

步骤（编号，可照着写）

以链式前向星 + Kahn 拓扑排序为例：

1. 读入 n（点数）、m（边数）。点编号按题目，0-based 或 1-based 都行，全篇统一。
2. 开数组：head[n] 初始化为 -1；to[m]、nxt[m]、w[m]（带权才要）；deg[n] 入度清零；cnt = 0 边计数器。
3. 加边 add(u, v, w)：

- to[cnt] = v; w[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt++;

- 若是无向图，再 add(v, u, w) 一次。

- 同时 deg[v]++（有向图只加被指向那端）。

1. 把所有 deg[i] == 0 的点入队（手写数组队列）。
2. 循环：出队 u，把 u 放进答案序列；遍历 u 的所有出边 i = head[u] ... i = nxt[i]，对 v = to[i] 做 if (--deg[v] == 0) q[tail++] = v;。
3. 结束后若答案长度 == n，输出答案；否则报告有环。

样例（一个具体小例子，带每步变化）

有向图，4 个点（1~4），边：1→3, 4→3, 2→4, 1→2, 2→3, 3→1。

先看这个图：1→2→3→1 构成环，所以不是 DAG，拓扑排序会失败。为了演示成功流程，改用边集：1→3, 1→2, 2→4, 4→3（无环）。

初始入度：deg[1]=0, deg[2]=1, deg[3]=2, deg[4]=1。

| 步骤 | 队列 | 出队 | 答案 | 入度变化 |

|---|---|---|---|---|

| 初始 | [1] | - | [] | deg = [0,1,2,1] |

| 1 | [] | 1 | [1] | 1→3: deg[3]=1；1→2: deg[2]=0，入队 |

| 2 | [2] | 2 | [1,2] | 2→4: deg[4]=0，入队 |

| 3 | [4] | 4 | [1,2,4] | 4→3: deg[3]=0，入队 |

| 4 | [3] | 3 | [1,2,4,3] | 无出边 |

答案长度 4 == n，成功。拓扑序 1 2 4 3（不唯一，1 2 3 4 也合法？不合法，因为 4→3 要求 4 在 3 前）。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（邻接表 + Kahn，好读版）：

from collections import deque

def topo_sort(n, edges):
    # edges: [(u, v), ...]，0-based 点编号
    g = [[] for _ in range(n)]
    deg = [0] * n
    for u, v in edges:
        g[u].append(v)
        deg[v] += 1
    q = deque(i for i in range(n) if deg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            deg[v] -= 1
            if deg[v] == 0:
                q.append(v)
    return order if len(order) == n else None  # None 表示有环

C++（链式前向星 + 手写队列，竞赛风）：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;   // 点数上限，按题目改
const int MAXM = 2e6 + 5;   // 边数上限（无向图要 ×2）

int head[MAXN], nxt[MAXM], to[MAXM], w[MAXM];
int deg[MAXN];              // 入度
int q[MAXN];                // 手写队列
int cnt = 0;                // 边计数器

void init(int n) {
    fill(head, head + n + 1, -1);
    fill(deg, deg + n + 1, 0);
    cnt = 0;
}

// 有向边 u -> v，权值 c
void add(int u, int v, int c = 0) {
    to[cnt] = v;
    w[cnt] = c;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}

// 返回 true 表示是 DAG，order 存拓扑序（长度 n）
bool topoSort(int n, vector<int>& order) {
    int h = 0, t = 0;
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 0) q[t++] = i;
    order.clear();
    order.reserve(n);
    while (h < t) {
        int u = q[h++];
        order.push_back(u);
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (--deg[v] == 0) q[t++] = v;
        }
    }
    return (int)order.size() == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;   // 不带权就删掉 c
        add(u, v, c);
        deg[v]++;             // 有向图只加被指向端
    }
    vector<int> order;
    if (topoSort(n, order)) {
        for (int x : order) cout << x << ' ';
        cout << '\n';
    } else {
        cout << "Cycle\n";
    }
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 建图：三种方式都是 O(n + m) 时间（邻接矩阵是 O(n²) 空间，初始化也要 O(n²)）。
• 拓扑排序（Kahn）：O(n + m)，每个点入队出队一次，每条边被扫一次。最好/平均/最坏一样。
• 空间：邻接矩阵 O(n²)；邻接表 O(n + m) 但带 vector 开销；链式前向星 O(n + m) 纯数组，常数最小。
• 常数：链式前向星 < 邻接表（vector<vector<int>>）< 邻接矩阵（n 大时直接爆）。1e6 点 2e6 边，链式前向星稳稳过；vector<vector<int>> 也能过但慢 2~3 倍。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「有 n 个任务，m 条依赖关系 a 必须在 b 之前完成」→ 拓扑排序判可行 + 输出顺序。
• 「判断有向图是否有环」→ Kahn 排完长度 < n 即有环。
• 「求最长链 / 最早开始时间」→ 拓扑序上 DP。
• 「字典序最小的拓扑序」→ 把队列换成小根堆（priority_queue + greater）。
• 「n, m ≤ 1e6，输入是边表」→ 链式前向星。
• 「n ≤ 100，多次询问 u, v 是否直接相连」→ 邻接矩阵。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// ===== 链式前向星 + Kahn 拓扑排序 模板 =====
const int MAXN = 1e6 + 5, MAXM = 2e6 + 5;
int head[MAXN], nxt[MAXM], to[MAXM], w[MAXM], deg[MAXN], q[MAXN], cnt;

void init(int n) {
    fill(head, head + n + 1, -1);
    fill(deg, deg + n + 1, 0);
    cnt = 0;
}
void add(int u, int v, int c = 0) {
    to[cnt] = v; w[cnt] = c; nxt[cnt] = head[u]; head[u] = cnt++;
}
bool topoSort(int n, vector<int>& order) {
    int h = 0, t = 0;
    for (int i = 1; i <= n; ++i) if (!deg[i]) q[t++] = i;
    order.clear(); order.reserve(n);
    while (h < t) {
        int u = q[h++]; order.push_back(u);
        for (int i = head[u]; i != -1; i = nxt[i])
            if (--deg[to[i]] == 0) q[t++] = to[i];
    }
    return (int)order.size() == n;
}

边界与易错点（WA 的常见原因，越具体越好）

1. 无向图边数要开两倍：MAXM 按 2m 开，add(u,v) 后必须再 add(v,u)，且 deg 两边都加。
2. 多测清空：head 要 fill(-1)，deg 要清零，cnt = 0。只清到 n 而不是 MAXN，否则 TLE。
3. 点编号 0-based 还是 1-based：模板里 for (i = 1; i <= n) 是 1-based；若题目给 0-based，要么整体 +1，要么改循环边界，别混。
4. nxt 和 next 重名：next 在 std 里有，别用 next 当变量名（有的编译器不报错但容易踩）。
5. 自环：u == v 的边会让 deg[u] 加 1，拓扑排序时永远出不来 → 正确判成有环，别以为是 bug。
6. 重边：链式前向星天然支持重边，不用去重；但如果题目要求去重（如最短路），要自己处理。
7. order.size() == n 判环：用 int 强转，size() 是 size_t，直接和 n（int）比有符号警告。
8. 队列开在全局：q[MAXN] 大小按点数开，别按边数。
9. long long：拓扑排序本身不涉及权值累加，但若在拓扑序上做 DP（最长路、方案数），DP 数组要 long long，取模题记得每步取模。
10. 字典序最小拓扑序：用 priority_queue<int, vector<int>, greater<int>> 替换手写队列，别用 set（常数大）。

同类题 / 变形（说清楚怎么改）

• 判环：直接跑 Kahn，返回 order.size() == n。
• 字典序最小拓扑序：队列换小根堆，其余不变。
• 拓扑序上 DP 求最长路：dp[v] = max(dp[v], dp[u] + w)，在出队 u 遍历出边时更新。
• 求方案数：cnt[v] = (cnt[v] + cnt[u]) % MOD，同样在遍历出边时累加。
• 反向拓扑：把边反向建，跑一遍，得到的是「所有后继都排完」的顺序，常用于求「最晚开始时间」。
• 分层拓扑（求每个点的最早完成轮次）：BFS 式拓扑，level[v] = max(level[v], level[u] + 1)。
• 邻接矩阵版：n ≤ 500 时直接 g[u][v] = 1，拓扑排序时 O(n²) 扫入度为 0 的点，简单粗暴。

常见坑

• 用 vector<vector<int>> 存 1e6 点 2e6 边，内存碎片 + 常数大，可能 TLE/MLE，换链式前向星。
• 用 map<int, vector<int>> 或 list 建图，常数爆炸，竞赛里绝对不要。
• #define int long long 导致 head 数组翻倍内存、fill 变慢，别用。
• 多测时 memset(head, -1, sizeof head) 清整个 MAXN，n 小的时候反而慢；用 fill(head, head + n + 1, -1)。
• 拓扑排序输出顺序不唯一，题目若要求「任意一个」就别纠结；要求「字典序最小」必须换堆。
• 输入边时 deg 加错端：有向图 u→v 加的是 deg[v]，不是 deg[u]。

拓展（变体、实际用途、面试常问）

• 实际用途：编译器依赖分析、Makefile 构建顺序、课程先修关系、包管理器依赖解析、电子表格公式求值。
• 面试常问：「如何检测循环依赖」→ Kahn 或 DFS 三色标记。
• DFS 版拓扑排序：后序遍历逆序输出，也能判环（遇到灰色节点即有环），但递归深度大时爆栈，竞赛里优先 Kahn。
• AOE 网 / 关键路径：拓扑序上正推最早时间、逆推最晚时间，求关键活动。
• 2-SAT：建蕴含图后跑 SCC（Tarjan/Kosaraju），和拓扑排序同源。
• 链式前向星的推广：所有「稀疏图 + 需要遍历邻边」的算法（最短路、网络流、Tarjan）都用它当底层存储。

自测 3 题（题目 + 折叠答案）

题 1：n=5, m=4，边 1→2, 2→3, 3→4, 4→5。输出任意一个拓扑序，并说明是否唯一。