拓扑排序

What · 是什么

拓扑排序将DAG（有向无环图）的所有节点排成线性序列，使得对任意有向边(u,v)，u在序列中位于v之前。常用Kahn算法（基于入度的BFS）或DFS后序逆序实现。拓扑排序不唯一。若图有环则不存在拓扑序。AOV网（顶点活动网）的拓扑排序可用于课程安排、任务调度等。AOE网可在此基础上求关键路径。

Why · 为什么

How · 实现

伪代码

Kahn:
  S ← {nodes with indeg=0}
  L ← []
  while S not empty:
    remove u from S, append to L
    for each edge (u,v):
      indeg[v] -= 1
      if indeg[v]==0: add v to S
  if len(L)<n: has cycle
  return L

Python 实现

from collections import deque
import sys

def topo_sort_kahn(n, edges):
    """Kahn's algorithm (BFS-based). Returns topological order or None if cycle."""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[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 adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None

def topo_sort_dfs(n, edges):
    """DFS-based topological sort. Returns order or None if cycle."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    UNVISITED, VISITING, DONE = 0, 1, 2
    state = [UNVISITED] * n
    order = []
    has_cycle = [False]
    def dfs(u):
        state[u] = VISITING
        for v in adj[u]:
            if state[v] == VISITING:
                has_cycle[0] = True
                return
            if state[v] == UNVISITED:
                dfs(v)
                if has_cycle[0]:
                    return
        state[u] = DONE
        order.append(u)
    for i in range(n):
        if state[i] == UNVISITED:
            dfs(i)
            if has_cycle[0]:
                return None
    order.reverse()
    return order

if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
    order = topo_sort_kahn(4, edges)
    assert order is not None
    assert order.index(0) < order.index(1)
    assert order.index(0) < order.index(2)
    assert order.index(1) < order.index(3)
    assert order.index(2) < order.index(3)
    order2 = topo_sort_dfs(4, edges)
    assert order2 is not None
    assert order2.index(0) < order2.index(1)
    # Cycle detection
    cycle_edges = [(0, 1), (1, 0)]
    assert topo_sort_kahn(2, cycle_edges) is None
    assert topo_sort_dfs(2, cycle_edges) is None
    print("topo-sort: ALL TESTS PASSED")

易错点

• 忘记检测环：Kahn算法中若len(order)<n则有环
• DFS方法中VISITING状态用于检测回边（环），DONE状态避免重复访问
• 多组数据需重置indeg数组
• 拓扑序不唯一，不同实现可能给出不同合法序列

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/topo/
• CP-Algorithms✓ https://cp-algorithms.com/graph/topological-sort.html
• 书籍✓ CPH ch16 pp159-166