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

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

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在