Python语言实现拓扑排序（Topological Sorting）算法

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))