Python实现对DAG G的拓扑排序

拓扑排序 示例：

对一个有向无环图（Directed Acyclic Graph，DAG）G实施拓扑排序，其本质是将图中的所有节点排列成一条线性序列，确保对于图中任意两个节点u与v，若存在边(u,v)属于G的边集，则u在该序列中必然位于v之前。一种可能得到的拓扑排序结果为：2->8->0->3->7->1->5->6->9->4->11->10->12。

算法分析

拓扑排序的实现步骤
在有向图中寻找一个没有前驱节点（即入度为零的顶点）并将其输出；
随后将该顶点从图中移除，并同时删除所有从该顶点出发的有向边；
按照上述过程不断重复，直至图中不再存在入度为零的顶点。

Python代码如下：

解法1：用邻接矩阵表示图的拓扑排序

    import numpy as np
    
    
    def topological_sort(g):
    n = len(g)
    # 获取所有入度为0的结点
    q = []
    for j in range(n):
        flag = True