§06 图状结构
拓扑排序
Kahn 算法：反复输出入度为 0 的顶点并删除其出边，直到全部顶点排成线性序列。适用于选课 依赖、工程工序等有向无环图（DAG）；顶点下方的数字实时显示当前入度，若序列排不满则说明 图中存在环。
拓扑排序
伪代码
1
procedure TopologicalSort(G)
2
indegree ← 计算各顶点入度
3
queue ← 所有 indegree 为 0 的顶点
4
while queue not empty do
5
u ← dequeue(queue); 输出 u
6
for each 出边 (u, v) do
7
indegree[v] ← indegree[v] - 1
8
if indegree[v] = 0 then enqueue(v)
9
end while
10
if 输出的顶点数 < n then 图中存在环
11
end procedure