拓扑排序 Topological Sort

2026-06-02

DAG 里给所有节点排个序,使得每条边都从靠前的指向靠后的。两种实现各背一份:Kahn 算法(BFS 入度法)和 DFS 后序逆序。顺手就把环检测做了。

直觉 — DAG 上的”先来后到”

拓扑排序解决的就一个问题:一堆有依赖关系的事,排出一个能挨个做完的顺序。

形式化点说:给定一张有向无环图(DAG),把所有节点排成一列,使得每一条边 u → v,u 都排在 v 前面。

类比:

选课:先修课排在后修课前面。
make 构建:被依赖的目标先编译。
任务调度:前置任务先做。

关键前提是无环。有环的话谁先谁后说不清,所以拓扑排序天然顺手能判 DAG。

下面的动画用 6 节点 DAG 0→2, 0→3, 1→3, 2→4, 3→4, 3→5 演示 Kahn 算法的全过程。重点盯两个东西:右侧的入度数组怎么变,和输出序列里节点入队的顺序。看完再回来读模板,代码就只是把动画里那几个动作翻译成 Python。

两种实现 — Kahn (BFS) 和 DFS 后序

Kahn 算法 — 入度为 0 的扔进队列

一句话:统计入度,把入度=0 的丢进队列;弹出一个就把它的邻居入度 -1,变 0 的再入队。

from collections import deque

def topo_sort_kahn(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []  # 空 = 有环

直观、可控、易改。要字典序最小的拓扑序,把 deque 换成最小堆 (heapq) 即可。

DFS 后序逆序 — 出栈顺序就是拓扑序

一句话:DFS 完一个节点就压栈,最后倒序就是拓扑序。

def topo_sort_dfs(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    color = [0] * n  # 0=白未访问, 1=灰在栈中, 2=黑完成
    order = []
    has_cycle = False

    def dfs(u):
        nonlocal has_cycle
        color[u] = 1
        for v in g[u]:
            if color[v] == 1:        # 灰碰灰 → 环
                has_cycle = True
            elif color[v] == 0:
                dfs(v)
        color[u] = 2
        order.append(u)              # 后序入栈

    for i in range(n):
        if color[i] == 0:
            dfs(i)
    return [] if has_cycle else order[::-1]

为什么后序逆序就是拓扑序?因为节点 u 在出栈前,它所有后继都已经出栈了。出栈晚的反而要排在前面,所以最后翻转一下。

怎么选

场景	选谁
想要稳定、可控、按层处理	Kahn
要字典序最小	Kahn + 最小堆
代码尽量短 / 顺便求 SCC	DFS
需要逆拓扑序(DAG DP 从汇点回推)	DFS(后序直接就是)
图非常大,递归怕爆栈	Kahn

顺便检测环 — 怎么用拓扑排序判 DAG

拓扑排序的副产物就是环检测,两种实现都自带,不需要另外写算法。

Kahn 法:跑完看 len(order)。如果 < n,说明还有节点入度永远 >0,被卡在环里出不来 → 有环。

1 2	`order = topo_sort_kahn(n, edges) is_dag = len(order) == n`

DFS 法:三色标记里灰碰灰就是环。因为灰色代表”在当前 DFS 路径上”,再次碰到灰色节点意味着走回了自己,形成了反向边(back edge)。

两点提醒:

无向图判环不能用拓扑排序(无向图没有”入度”的概念),用并查集或 DFS 看是否有非父节点的访问。
只判环不输出序时,Kahn 法可以只数计数,不存 order,省点内存。

经典题 — 课程表 / 任务调度

LC 207. 课程表:给你 numCourses 和先修关系 prerequisites = [[a, b], ...](修 a 之前要先修 b),问能不能修完。本质就是判 DAG。

class Solution:
    def canFinish(self, n, prerequisites):
        g = [[] for _ in range(n)]
        indeg = [0] * n
        for a, b in prerequisites:
            g[b].append(a)            # 先修 b 才能修 a,所以边 b→a
            indeg[a] += 1
        q = deque(i for i in range(n) if indeg[i] == 0)
        done = 0
        while q:
            u = q.popleft()
            done += 1
            for v in g[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return done == n

LC 210. 课程表 II:同样的图,输出修课顺序。把 done += 1 换成 order.append(u),最后 return order if len(order) == n else []。

易踩坑:边的方向。题目说”修 a 前要先修 b”,意思是 b 是 a 的先修,所以图里应该是 b → a(b 排在 a 前)。方向画反一遍 WA 是经典操作。

其他必刷:

LC 802. 找到最终的安全状态 — 反图 + 拓扑,定义安全 = 所有路径都终止
LC 269. 火星词典 — 从相邻单词的第一个不同字符建边,跑拓扑
LC 310. 最小高度树 — 类拓扑,每轮剥掉叶子(度=1),最后剩 1~2 个就是答案
LC 329. 矩阵中的最长递增路径 — DAG 上 DP,可用记忆化 DFS 或拓扑序递推
LC 2192. 有向无环图中一个节点的所有祖先 — 拓扑序上做集合合并
LC 1857. 有向图中最大颜色值 — 拓扑序 + 颜色计数 DP,自带环检测

记忆法

一句话:入度 0 的先走,走一个减一圈。

三个对仗:

维度	Kahn (BFS)	DFS 后序
入口	入度为 0 的点入队	任选未访问节点 DFS
推进	出队 → 邻居入度 -1	递归到底 → 出栈
判环	输出数 < n	灰碰灰
顺序	自然得到拓扑序	后序数组翻转

判题口诀:

看到”先修”、”依赖”、”前置任务” → 拓扑排序。
题目问”能否完成” → 判环就够,Kahn 数计数。
题目问”输出顺序” → Kahn 存 order,或 DFS 后序逆。
要求”字典序最小” → Kahn 把 deque 换 heapq。
DAG 上做 DP → 按拓扑序递推,前驱已算好,直接转移。

记住一件事:拓扑排序不是排序算法,是依赖求解算法。它产生的”序”是一个合法的执行顺序,可能不唯一。