拓扑排序笔记

发表于 2023-02-23 更新于 2023-09-25 分类于算法，笔记本文字数： 809 阅读时长 ≈ 5 分钟

给图的节点排序——拓扑排序

简介

拓扑排序（Topological sorting）

适用场景：

判断图中有无环

定义：

在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点\(u\)到\(v\) 的有向边\((u,v)\), 都可以有\(u\)在\(v\)的前面。

学生课表是一个非常典型的例子，某位学生想要修A课程，可能需要先修 x,y,z三门课程，这些课程作为A课程的前置课程，此时x,y,z三门课程作为节点指向A课程节点，拓扑排序下节点的顺序就是x,y,z在A的前面，xyz三个节点的位置随便。

代码模版：

import collections


def topo_sort(n,edges):
    '''拓扑排序,bfs遍历
    
    Args:
        n: n个节点,节点的值 0~(n-1)
        edges: 节点之间的关系
    
    Returns:
        一个拓扑排序后的序列列表
    '''
    in_nums = [0]*n # 统计各个节点的入度数
    graph = [[] for _ in range(n)] # 图
    for edge in edges:
        x,y = edge 
        in_nums[y] += 1
        graph[x].append(y)

    q = collections.deque()
    # 初始化队列，入度为0的进入队列
    for i in range(n):
        if in_nums[i] == 0:
            q.appendleft(i)
    ans = []
    while q:
        cur_node = q.pop()
        ans.append(cur_node)
        # 拿走一个节点后，需要删除这个节点指向其他节点的边
        for x in graph[cur_node]:
            in_nums[x] -= 1
            if in_nums[x] == 0:
                q.appendleft(x)
    return ans

简介

参考资料