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

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

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

有向無(wú)環(huán)圖

拓?fù)渑判蚴轻槍?duì)有向無(wú)環(huán)圖（DAG, Directed Acyclic Graph）的

具有以下性質(zhì)：

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

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

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

算法步驟

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

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

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

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

代碼實(shí)現(xiàn)

對(duì)于下圖：

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]