日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

拓撲排序Python實現的過程_python

作者：johnjim0816 ? 更新時間： 2023-03-27 編程語言

有向無環圖

拓撲排序是針對有向無環圖（DAG, Directed Acyclic Graph）的

具有以下性質：

  • 如果這個圖不是 DAG，那么它是沒有拓撲序的；
  • 如果是 DAG，那么它至少有一個拓撲序；
  • 反之，如果它存在一個拓撲序，那么這個圖必定是 DGA。

拓撲排序

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。

通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。

簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

算法步驟

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

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

可以理解為入度為0的點就是起點，拓撲排序步驟如下：

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

代碼實現

對于下圖：

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 ("拓撲排序結果：")
g.topologicalSort() # 結果為[5, 4, 2, 3, 1, 0]

總結

原文鏈接：https://johnjim0816.blog.csdn.net/article/details/121047511

欄目分類
最近更新