4.5 拓扑排序与强连通分量：DAG 的秩序

4.5 拓扑排序与强连通分量：DAG 的秩序

本节摘要：有向无环图（DAG）表达"先于"关系，拓扑排序把它拉直成一条合法执行序列。Kahn 算法反复摘除入度为零的顶点（没有未完成的前置），天然能检测环路；DFS 则按完成时刻的逆序给出另一种合法序。强连通分量（SCC）把"互相可达"的顶点归成一团，配合缩图，能把任意有向图化简为 DAG 处理。本节实现 Kahn 与 Kosaraju 两套功法。

先修课表是张有向图

排课系统要回答的问题：课程之间有先修关系（学"编译原理"前须先修"数据结构"），怎么排出一个顺序，让每门课开课时它的先修课都已完成？把课程当顶点、先修关系当有向边（先修 → 后续），问题变成：给有向图的顶点排一个线性序，使每条边的起点都排在终点前面——拓扑排序。

它有解当且仅当图无环。环意味着"A 等 B，B 又等 A"，谁也开不了课。所以拓扑排序的每一份实现都必须兼职环检测：构建系统报循环依赖、包管理器报死锁、Excel 报循环引用，底层都是同一个判断。

# Kahn 算法：反复摘除入度为零的顶点
from collections import deque

def topo_kahn(n, edges):
    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)
        print(f"输出 {u}（入度归零），剩余入度 {indeg}")
        for v in adj[u]:
            indeg[v] -= 1               # 后续课的一门前置完成
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # 摘不完 = 有环

edges = [(0, 2), (1, 2), (2, 3), (1, 4), (3, 5), (4, 5)]
order = topo_kahn(6, edges)
print("拓扑序：", order)
# 输出（中间行略，共六行）：
# 拓扑序： [0, 1, 2, 4, 3, 5]
# 每门课输出时，其先修课都已在序列前部；注意 2 只能在 0 与 1 之后

# 加一条 5→1 造一个环：课 1 等课 5，课 5 又等课 1
print("有环时：", topo_kahn(6, edges + [(5, 1)]))
# 输出：有环时： None
# 队列提前清空：0 之外无人入度归零，环上课程永远等不到前置
​

Kahn 的每条边只在"起点被摘除"时被查看一次，复杂度 O(V+E)。输出的 [0, 1, 2, 4, 3, 5] 只是众多合法序之一——同一张 DAG 的合法拓扑序可以有很多种（交换互不相干的顶点即可），别把某个具体输出当成唯一答案。

另一条路是 DFS：对 DAG 做深度优先，按完成时刻从晚到早排列顶点，恰好是一条合法拓扑序（一个顶点完成，意味着它所有后继都已探索完毕，它自然排在前）。工程上 Kahn 更直观且自带环检测，DFS 版常见于 Tarjan 强连通算法的骨架。

强连通分量：互相可达的一家人

有环怎么办？先看清环长什么样。强连通分量把有向图划分成若干团：团内任意两点互相可达。分量的骨架之间只剩单向边——把每个分量缩成一个超级点，任意有向图就坍缩成一张 DAG。这招叫缩点，是处理有环有向图的标准起手式：算传递关系、求最长链、判定可达性，都先缩点再按 DAG 做。

# Kosaraju 算法：两趟 DFS 找强连通分量
def kosaraju(n, edges):
    adj = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        radj[v].append(u)               # 反向图：所有边掉头

    visited = [False] * n
    finish = []                          # 第一趟：记录完成时刻
    def dfs1(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        finish.append(u)                 # 后进先出的"完成栈"

    for s in range(n):
        if not visited[s]:
            dfs1(s)

    visited2 = [False] * n
    comps = []
    for u in reversed(finish):           # 第二趟：完成时刻从晚到早
        if visited2[u]:
            continue
        comp, stack = [], [u]
        visited2[u] = True
        while stack:                     # 在反向图上收集团块
            x = stack.pop()
            comp.append(x)
            for y in radj[x]:
                if not visited2[y]:
                    visited2[y] = True
                    stack.append(y)
        comps.append(sorted(comp))
    return comps

# 两团互相可达的顶点 + 单向桥：0→1→2→0 成环，3↔4 成环，2→3 单向
E = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 3)]
print("强连通分量：", kosaraju(5, E))
# 输出：强连通分量： [[0, 1, 2], [3, 4]]
# 团内互相可达；团间只有 2→3 一条单向边——缩点后就是 DAG
​

为什么两趟方向相反的 DFS 能拆出分量？直觉账：第一趟按完成时刻把"靠出口近"的顶点压在栈底、"靠深处"的压在栈顶；反向图恰好堵住出口，从栈顶出发在反向图里能到达的，恰是原方向上能回到起点的那些——正反都通，正是强连通的定义。两趟各 O(V+E)。

⚠️ 常见坑：拿到依赖数据就直接跑拓扑排序。数据来自用户或外部系统时，环是常态而非异常——Kahn 的"摘不完"判断必须触发报错路径并指出环上顶点，而不是返回残缺序列假装成功。定位环的具体成员，可用 SCC：规模大于一的分量就是环。

💡 关键直觉：入度是"还有几个前置没完成"的计数器，Kahn 每摘一个顶点就给它的后继减一——这个视角让拓扑排序可以自然改写成"分层处理"（每个时刻所有入度零的顶点同批执行），正是并行任务调度的骨架。

走火入魔：把 DAG 的结论用在有环图上

**事故一：DFS 完成逆序不检测环。**对有环图跑"DFS 完成逆序"照样会输出一个序列，但它不再是合法拓扑序——算法本身没有报警功能。用 DFS 求拓扑序时必须辅以环检测（递归栈中重访灰色顶点即环），否则错误静默扩散到下游调度器。

**事故二：缩点后忘记建新图。**SCC 拆出来只是第一步，"把分量当超级点重建边"（注意去重与去掉分量内部边）才得到 DAG。跳过这一步直接在原图上做 DAG 算法，环还在，结论照错。

本节要点回顾

• 拓扑排序：DAG 顶点的线性序，每条边起点在前；有解当且仅当无环，因此实现必须兼职环检测；
• Kahn 入度法：反复摘入度零顶点、给后继减一，O(V+E)，摘不完即有环；输出只是合法序之一；
• DFS 完成逆序是另一条合法序，但对有环图会静默出错，须配灰色标记检测；
• 强连通分量：团内互相可达；Kosaraju 两趟相反方向的 DFS，各 O(V+E)；
• 缩点成 DAG 是处理有环有向图的标准起手式，构建系统与依赖解析的循环依赖定位都靠它。

图论四章功法圆满。下一章回到最古老的战场：把一堆乱序数据变成有序——排序与查找的内功大比拼。