Kahn 算法是一种直观的拓扑排序方法，它模拟了任务执行的过程：总是先执行那些没有前置依赖的任务。 算法的关键在于维护每个节点的 入度 (In-degree)，即有多少条边指向该节点。
初始化:
计算所有节点的入度 in_degree[v]
创建一个队列 Q
将所有 in_degree[v] == 0 的节点 v 加入 Q
创建一个列表 L 用于存储结果
循环:
while Q 不为空:
从 Q 中取出一个节点 u
将 u 加入 L
for 每个 u 的邻居 v:
in_degree[v] = in_degree[v] - 1
if in_degree[v] == 0:
将 v 加入 Q
检查:
if L 中的节点数 == 图中总节点数:
返回 L (拓扑排序结果)
else:
图中存在环，无法拓扑排序
function KahnTopologicalSort(Graph G):
L = [] // 存储排序结果的列表
in_degree = map() // 存储每个节点的入度
queue = Queue() // 存储入度为 0 的节点
// 1. 计算所有节点的入度
for each node u in G:
in_degree[u] = 0
for each node u in G:
for each neighbor v of u:
in_degree[v] = in_degree[v] + 1
// 2. 将所有入度为 0 的节点加入队列
for each node u in G:
if in_degree[u] == 0:
queue.enqueue(u)
// 3. 处理队列中的节点
while not queue.isEmpty():
u = queue.dequeue()
L.append(u)
// 4. 更新邻居的入度
for each neighbor v of u:
in_degree[v] = in_degree[v] - 1
if in_degree[v] == 0:
queue.enqueue(v)
// 5. 检查是否存在环
if len(L) == G.numberOfNodes():
return L // 成功找到拓扑排序
else:
return Error("Graph contains a cycle") // 图中有环
优点: 实现相对简单，容易理解。可以同时检测图中是否存在环。
缺点: 需要额外空间存储入度和队列。
基于深度优先搜索 (DFS) 的拓扑排序利用了 DFS 完成节点访问的顺序特性。其核心思想是：一个节点必须在其所有后续依赖节点都被访问（并加入结果）之后，才能被加入最终的拓扑序列。
具体来说，当 DFS 访问到一个节点 `u` 时：
因为节点是在其所有后继节点被处理完后才加入结果列表的头部，所以最终列表的顺序就是拓扑排序的一个有效序列。
Graph: A -> B, A -> C, B -> D, C -> D
DFS(A):
Mark A as visiting
DFS(B):
Mark B as visiting
DFS(D):
Mark D as visiting
(D has no unvisited neighbors)
Mark D as visited
Add D to front of result: [D]
Mark B as visited
Add B to front of result: [B, D]
DFS(C):
Mark C as visiting
DFS(D): (D is already visited, skip)
Mark C as visited
Add C to front of result: [C, B, D]
Mark A as visited
Add A to front of result: [A, C, B, D]
Final Result: A, C, B, D (One possible topological sort)
function DFSTopologicalSort(Graph G):
L = [] // 存储排序结果的列表 (最终需要反转或头部插入)
visited = set() // 记录已完全访问的节点
visiting = set() // 记录当前递归栈中的节点 (用于检测环)
has_cycle = false
function dfs_visit(node u):
if u in visiting: // 检测到环
has_cycle = true
return
if u in visited: // 已访问过，直接返回
return
visiting.add(u) // 标记为正在访问
for each neighbor v of u:
if not has_cycle:
dfs_visit(v)
else:
return // 如果已检测到环，提前退出
visiting.remove(u) // 从递归栈中移除
visited.add(u) // 标记为已访问
L.insert(0, u) // 将节点插入结果列表的头部
// 对图中每个节点启动 DFS
for each node u in G:
if u not in visited and not has_cycle:
dfs_visit(u)
if has_cycle:
return Error("Graph contains a cycle")
else:
return L // 返回拓扑排序结果
优点: 通常比 Kahn 算法需要更少的额外空间（如果使用递归栈），代码可能更简洁。也能检测环。
缺点: 理解上可能比 Kahn 算法稍复杂，递归深度可能受限。
假设图有 V 个顶点和 E 条边。
结论：两种主要的拓扑排序算法都具有线性时间复杂度 O(V + E)，效率都很高。
结论：两种算法的空间复杂度也都是线性的 O(V)。
时间复杂度 (Time Complexity): O(V + E)
空间复杂度 (Space Complexity): O(V)
(V = 顶点数, E = 边数)
拓扑排序是图论中的基础算法，但它还有一些有趣的变种和更广泛的应用。