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

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

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

有向無環(huán)圖

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

具有以下性質(zhì)：

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

拓?fù)渑判?/h2>
對(duì)一個(gè)有向無環(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)單的說，由某個(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)為止。后一種情況說明有向圖中必然存在環(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]

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章:

拓?fù)渑判?/a>

Python

相關(guān)文章

在Python的Django框架中獲取單個(gè)對(duì)象數(shù)據(jù)的簡(jiǎn)單方法
這篇文章主要介紹了在Python的Django框架中獲取單個(gè)對(duì)象數(shù)據(jù)的簡(jiǎn)單方法,Django為數(shù)據(jù)的操作提供了諸多方便的功能,需要的朋友可以參考下
2015-07-07
python使用MkDocs自動(dòng)生成文檔的操作方法
python代碼注釋風(fēng)格有很多,比較主流的有 reStructuredText風(fēng)格、numpy風(fēng)格、Google風(fēng)格,自動(dòng)生成文檔的工具也有很多,常見的有：Pydocs,Sphinx和MkDocs,本文給大家介紹了python使用MkDocs自動(dòng)生成文檔的操作方法,需要的朋友可以參考下
2024-06-06
Python上下文管理器實(shí)現(xiàn)方法總結(jié)
在本篇文章里小編給大家整理的是關(guān)于Python上下文管理器實(shí)現(xiàn)方法總結(jié)內(nèi)容，有興趣的朋友們可以學(xué)習(xí)參考下。
2021-07-07
Pycharm 設(shè)置默認(rèn)頭的圖文教程
今天小編就為大家分享一篇Pycharm 設(shè)置默認(rèn)頭的圖文教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2019-01-01
在DigitalOcean的服務(wù)器上部署flaskblog應(yīng)用
這篇文章主要介紹了在DigitalOcean的服務(wù)器上部署flaskblog的方法,flaskblog是用Python的Flask開發(fā)的一個(gè)博客程序,而DigitalOcean則是大受歡迎的SSD主機(jī)提供商,需要的朋友可以參考下
2015-12-12
Django零基礎(chǔ)入門之路由path和re_path詳解
這篇文章主要介紹了Django零基礎(chǔ)入門之路由path和re_path，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2021-09-09
如何解決Pycharm編輯內(nèi)容時(shí)有光標(biāo)的問題
文章介紹了如何在PyCharm中配置VimEmulator插件,包括檢查插件是否已安裝、下載插件以及安裝IdeaVim插件的步驟
2025-02-02
Python從文件中讀取指定的行以及在文件指定位置寫入
這篇文章主要給大家介紹了關(guān)于Python從文件中讀取指定的行及在文件中指定位置寫入的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用Python具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
2019-09-09
用python實(shí)現(xiàn)名片管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了用python實(shí)現(xiàn)名片管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-06-06
python程序中調(diào)用其他程序的實(shí)現(xiàn)
本文主要介紹了python程序中調(diào)用其他程序的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2023-02-02