問題:有向無環圖的拓撲排序

題目描述
由某個集合上的一個偏序得到該集合上的一個全序，這個操作被稱為拓撲排序。偏序和全序的定義分別如下：
若集合X上的關系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系。
設R是集合X上的偏序，如果對每個x,y∈X必有xRy或yRx，則稱R是集合X上的全序關系。
由偏序定義得到拓撲有序的操作便是拓撲排序。
拓撲排序的流程如下：

在有向圖中選一個沒有前驅的頂點并且輸出之；

從圖中刪除該頂點和所有以它為尾的弧。

重復上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。后一種情況則說明有向圖中存在環。
采用鄰接表存儲有向圖，并通過棧來暫存所有入度為零的頂點，可以描述拓撲排序的算法如下：

在本題中，讀入一個有向圖的鄰接矩陣（即數組表示），建立有向圖并按照以上描述中的算法判斷此圖是否有回路，如果沒有回路則輸出拓撲有序的頂點序列。

輸入
輸入的第一行包含一個正整數n，表示圖中共有n個頂點。其中n不超過50。
以后的n行中每行有n個用空格隔開的整數0或1，對于第i行的第j個整數，如果為1，則表示第i個頂點有指向第j個頂點的有向邊，0表示沒有i指向j的有向邊。當i和j相等的時候，保證對應的整數為0。
輸出
如果讀入的有向圖含有回路，請輸出“ERROR”，不包括引號。
如果讀入的有向圖不含有回路，請按照題目描述中的算法依次輸出圖的拓撲有序序列，每個整數后輸出一個空格。
請注意行尾輸出換行。
樣例輸入
4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0
樣例輸出
3 0 1 2

n=0 G=[[] for i in range(100)] inDegree=[0]*100 def topologicalSort():global n,G,inDegreelist=[]list_1=[]num=0for i in range(0,n):if inDegree[i]==0:list.append(i)while len(list)!=0:t=list[-1]list_1.append(t)list.pop(-1)for i in range(len(G[t])):v=G[t][i]inDegree[v]-=1if inDegree[v]==0:list.append(v)G[t].clear()num+=1if num==n:for i in list_1:print(i,end=' ')else:print("ERROR") if __name__=='__main__':n = int(input())for i in range(0, n):ar = input()b = ar.split(' ')graph = [int(i) for i in b]for j in range(len(graph)):if graph[j] == 1 and i!=j:inDegree[j]+=1G[i].append(j)topologicalSort()print()

總結

以上是生活随笔為你收集整理的有向无环图拓扑排序(python实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。