【GD】拓扑排序 python实现

无名

拓扑排序是指在有向无环图中，把所有结点按照一定的排序排成一列，使得左边的点都指向右边的点。
一般有两种方法做拓扑排序
Kahn算法
用一个一维数组存每个结点的入度。用一个数据结构（随意都可以，数组，栈，列表等等）存储所有入度为0的结点。每次从入度为0的结点出发，记录路径，删除该结点，把该结点指向的点的入度减1，再找入度为0的结点，存进数据结构。再循环操作，直到找不到入度为0的结点就停止，如果还剩结点或者路径长度不够，说明该图不是有向无环图。
注意：如果是要打印字典序排序，就用优先列表存入度为0的结点

DFS深搜
从任意未被访问的结点出发做深搜。回溯的时候记录记录路径，得到的路径再倒序一下就是正确的拓扑排序。直到所有结点都被访问完，每次深搜的倒序路径拼接在一起就是答案。

样例图片
python代码：
from queue import PriorityQueue as pQueue
import sys

sys.setrecursionlimit(100000)

# 这是最常见的拓扑排序，0入度集合可以用队列，栈等等，只要能存储0入度的点就行
# 这里用了队列，其实就是跟广搜bfs差不多，入度为0的才入队
def ts_bfs(inDegrees, graph):
    n = len(graph)
    result = ''
    q = []
    vis = [False] * n
    for i, inDegree in enumerate(inDegrees):
        if inDegree == 0:
            q.append(i)
            vis = True
    while q:
        s = q.pop(0)
        result += str(s)
        for sub in graph:
            if not vis[sub]:
                inDegrees[sub] -= 1
                if inDegrees[sub] == 0:
                    q.append(sub)
    return result if len(result) == n else 'The graph is not DAG'

# 满足拓扑排序下，序号从小到大排序或字典序排序
def ts_bfs_pq(inDegrees, graph):
    n = len(graph)
    result = ''
    q = pQueue()
    vis = [False] * n
    for i, inDegree in enumerate(inDegrees):
        if inDegree == 0:
            q.put(i)
            vis = True
    while not q.empty():
        s = q.get()
        result += str(s)
      
来自于互联网!