对有向无环图(DAG)进行拓扑排序(Topological So

定义：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：

1. 每个顶点出现且只出现一次；
2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

算法基本思想：
step1:根据邻接矩阵，计算每个点的入度，并将入度为0的点存于列表zero中
step2:输出该点后，从zero中删除该点和以其为顶点的所有边
step3:将除已删除的点外，入度为0的点存于列表zero
step4:重复setp2和step3，直至所有点都已经输出或者不存在入度为0的点

import numpy as np

def topological_sorting(G):
    ##计算每个点的入度
    indegree = []
    for i in range(len(G)):
        indegree.append(np.sum(G[:,I]))
    
    result = []
    zero = []
    for i in range(len(indegree)):
        if indegree[i] == 0:
            zero.append(i)
    #print(zero)
    
    while(len(zero) != 0):
        curr = zero[-1]
        zero.pop()
        result.append(curr)
        temp = []
        for i in range(len(G)):
            if G[curr][i] != 0:
                temp.append(i)
                indegree[i] = indegree[i] - 1
        for i in range(len(temp)):
            if indegree[temp[i]] == 0:
                zero.append(temp[I])
    
    for i in range(len(result)):
        result[i] = result[i] + 1
           
    if len(result) == len(G):
        print("Tt is a DAG")
        return result
    else:
        print("It is not a DAG")
        return False

测试1：

demo.png

G = np.array([[0,1,0,1,0],
              [0,0,1,1,0],
              [0,0,0,0,1],
              [0,0,1,0,1],
              [0,0,0,0,0]])

result = topological_sorting(G)

result.png

测试2：

demo2.png

G = np.array([[0,1,0,0],
              [0,0,1,0],
              [0,0,0,1],
              [1,0,0,0]])

result = topological_sorting(G)

result2.png