Python语言实现拓扑排序(Topological Sorting)算法
拓扑排序是对有向无环图(DAG)顶点的一种线性排序,使得对于每一条从顶点 uuu 到顶点 vvv 的有向边, uuu 都排在 vvv 之前。常用的拓扑排序算法有Kahn算法和深度优先搜索(DFS)算法。下面是这两种算法的Python实现。
Kahn算法
Kahn算法利用入度的概念,逐步删除入度为0的节点。
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
in_degree = [0] * n
adj_list = defaultdict(list)
for u, v in edges:
adj_list[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
topo_sort = []
while queue:
u = queue.popleft()
topo_sort.append(u)
for v in adj_list[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(topo_sort) == n:
return topo_sort
else:
return [] # 图中存在环,无法进行拓扑排序
# 示例用法
n = 6
edges = [
(5, 2),
(5, 0),
(4, 0),
(4, 1),
(2, 3),
(3, 1)
]
print("Kahn's Topological Sort:", kahn_topological_sort(n, edges))