拓?fù)渑判騊ython實現(xiàn)的過程

更新時間：2023年01月31日 09:44:55 作者：johnjim0816

這篇文章主要介紹了拓?fù)渑判騊ython實現(xiàn)的過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

有向無環(huán)圖

拓?fù)渑判蚴轻槍τ邢驘o環(huán)圖（DAG, Directed Acyclic Graph）的

具有以下性質(zhì)：

如果這個圖不是 DAG，那么它是沒有拓?fù)湫虻模?/li>
如果是 DAG，那么它至少有一個拓?fù)湫颍?/li>
反之，如果它存在一個拓?fù)湫?，那么這個圖必定是 DGA。

拓?fù)渑判?/h2>
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。

通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄小?/p>
簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判颉?/p>

算法步驟

在講算法步驟之前先了解入度與出度的概念：

入度：頂點的入度是指「指向該頂點的邊」的數(shù)量；
出度：頂點的出度是指該頂點指向其他點的邊的數(shù)量。

可以理解為入度為0的點就是起點，拓?fù)渑判虿襟E如下：

從 DAG 圖中選擇一個入度為0的頂點并輸出；
從圖中刪除該頂點和所有以它為起點的有向邊；
重復(fù) 1 和 2 直到當(dāng)前的 DAG 圖為空或當(dāng)前圖中不存在入度為0的頂點為止。后一種情況說明有向圖中必然存在環(huán)

代碼實現(xiàn)

對于下圖：

from collections import defaultdict 
 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self,v,visited,stack): 
  
        visited[v] = True
  
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        print (stack) 
  
g= Graph(6) 
g.addEdge(5, 2); 
g.addEdge(5, 0); 
g.addEdge(4, 0); 
g.addEdge(4, 1); 
g.addEdge(2, 3); 
g.addEdge(3, 1); 
  
print ("拓?fù)渑判蚪Y(jié)果：")
g.topologicalSort() # 結(jié)果為[5, 4, 2, 3, 1, 0]