python實現(xiàn)拓?fù)渑判虻幕窘坛?/h1>

 更新時間：2018年03月11日 09:51:50   作者：趙潔鈺Amy  

拓?fù)渑判蚴菍τ邢驘o環(huán)圖的一種排序，發(fā)現(xiàn)自己并沒有真的理解拓?fù)渑判颍俅螌W(xué)習(xí)了下，所以下面這篇文章主要給大家介紹了關(guān)于python實現(xiàn)拓?fù)渑判虻幕窘坛?，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下，

拓?fù)渑判?/strong>

幾乎在所有的項目，甚至日常生活，待完成的不同任務(wù)之間通常都會存在著某些依賴關(guān)系，這些依賴關(guān)系會為它們的執(zhí)行順序行程表部分約束。對于這種依賴關(guān)系，很容易將其表示成一個有向無環(huán)圖（Directed Acyclic Graph，DAG，無環(huán)是一個重要條件），并將尋找其中依賴順序的過程稱為拓?fù)渑判颍╰opological sorting）。

拓?fù)渑判蛞獫M足如下兩個條件

• 每個頂點出現(xiàn)且只出現(xiàn)一次。
• 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。

拓?fù)渑判蛩惴?/strong>

任何無回路的頂點活動網(wǎng)（AOV網(wǎng)）N都可以做出拓?fù)湫蛄校?/p>

• 從N中選出一個入度為0的頂點作為序列的下一頂點。
• 從N網(wǎng)中刪除所選頂點及其所有的出邊。
• 反復(fù)執(zhí)行上面兩個步驟，知道已經(jīng)選出了圖中的所有頂點，或者再也找不到入度為非0的頂點時算法結(jié)束。

如果剩下入度非0的頂點，就說明N中有回路，不存在拓?fù)渑判颉?br />

存在回路，意味著某些活動的開始要以其自己的完成作為先決條件，這種現(xiàn)象成為活動之間的死鎖。一種常見的頂點活動網(wǎng)實例是大學(xué)課程的先修課程。課程知識有前后練習(xí)，一門課可能以其他課程的知識為基礎(chǔ)，學(xué)生想選修這門課程時，要看是否已修過所有先修課程。如果存在一個回路的話，那就意味著進入了一個循環(huán)，那么該同學(xué)就畢不了業(yè)了。

因此可以說拓?fù)渑判蛩惴ㄊ菫榱俗龀鰸M足制約關(guān)系的工作安排。

下面我們操作一個實例，如下圖是一個有向無環(huán)圖：

用字典表示：G = { 'a':'bce', 'b':'d','c':'d','d':'','e':'cd'}

代碼實現(xiàn)：

def toposort(graph):
 in_degrees = dict((u,0) for u in graph) #初始化所有頂點入度為0
 vertex_num = len(in_degrees)
 for u in graph:
  for v in graph[u]:
   in_degrees[v] += 1  #計算每個頂點的入度
 Q = [u for u in in_degrees if in_degrees[u] == 0] # 篩選入度為0的頂點
 Seq = []
 while Q:
  u = Q.pop()  #默認(rèn)從最后一個刪除
  Seq.append(u)
  for v in graph[u]:
   in_degrees[v] -= 1  #移除其所有指向
   if in_degrees[v] == 0:
    Q.append(v)   #再次篩選入度為0的頂點
 if len(Seq) == vertex_num:  #如果循環(huán)結(jié)束后存在非0入度的頂點說明圖中有環(huán)，不存在拓?fù)渑判?
  return Seq
 else:
  print("there's a circle.")
G = {
 'a':'bce',
 'b':'d',
 'c':'d',
 'd':'',
 'e':'cd'
}
print(toposort(G))

輸出結(jié)果：

['a', 'e', 'c', 'b', 'd']

圖中有環(huán)的情況：

G = { 'a':'bce', 'b':'d','c':'d','d':'e','e':'cd'}

輸出結(jié)果：

there's a circle.
None

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章:

• Python實現(xiàn)經(jīng)典算法拓?fù)渑判?、字符串匹配算法和最小生成樹實?/a>
• 拓?fù)渑判騊ython實現(xiàn)的過程
• Python關(guān)于拓?fù)渑判蛑R點講解
• python實現(xiàn)拓?fù)渑判虻姆椒ú襟E

• 拓?fù)?/a>
• 排序
• python

相關(guān)文章

• 

  跟老齊學(xué)Python之重回函數(shù)

  在本教程的開始部分，就已經(jīng)引入了函數(shù)的概念：《永遠(yuǎn)強大的函數(shù)》，之所以那時候就提到函數(shù)，是因為我覺得函數(shù)之重要，遠(yuǎn)遠(yuǎn)超過一般。這里，重回函數(shù)，一是復(fù)習(xí)，二是要在已經(jīng)學(xué)習(xí)的基礎(chǔ)上，對函數(shù)有更深刻的理解。

  2014-10-10
• 

  詳解Python如何實現(xiàn)發(fā)送帶附件的電子郵件

  SMTP（Simple Mail Transfer Protocol）即簡單郵件傳輸協(xié)議,它是一組用于由源地址到目的地址傳送郵件的規(guī)則，由它來控制信件的中轉(zhuǎn)方式。本文將利用SMTP實現(xiàn)發(fā)送帶附件的電子郵件，感興趣的可以了解一下

  2023-04-04
• 

  python保存二維數(shù)組到txt文件中的方法

  今天小編就為大家分享一篇python保存二維數(shù)組到txt文件中的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

  2018-11-11
• 

  python fabric實現(xiàn)遠(yuǎn)程操作和部署示例

  這篇文章主要介紹了python使用fabric實現(xiàn)遠(yuǎn)程操作和部署示例,需要的朋友可以參考下

  2014-03-03
• 

  詳解python中的hashlib模塊的使用

  這篇文章主要介紹了python中的hashlib模塊的使用，非常不錯，具有一定的參考借鑒價值 ,需要的朋友可以參考下

  2019-04-04
• 

  Python多進程編程multiprocessing代碼實例

  這篇文章主要介紹了Python多進程編程multiprocessing代碼實例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

  2020-03-03
• 

  Python網(wǎng)絡(luò)請求模塊urllib與requests使用介紹

  網(wǎng)絡(luò)爬蟲的第一步就是根據(jù)URL，獲取網(wǎng)頁的HTML信息。在Python3中，可以使用urllib和requests進行網(wǎng)頁數(shù)據(jù)獲取，這篇文章主要介紹了Python網(wǎng)絡(luò)請求模塊urllib與requests使用

  2022-10-10
• 

  Python中日期和時間的互相轉(zhuǎn)換操作方法

  Python的datetime模塊提供了一套強大而靈活的工具,使我們能夠輕松地在不同的時間表示形式間相互轉(zhuǎn)換,并進行復(fù)雜的時間計算,本文通過一個實用的例子向大家展示如何在Python中高效地進行這些操作,感興趣的朋友一起看看吧

  2024-05-05
• 

  Python爬蟲使用Selenium+PhantomJS抓取Ajax和動態(tài)HTML內(nèi)容

  這篇文章主要介紹了Python爬蟲使用Selenium+PhantomJS抓取Ajax和動態(tài)HTML內(nèi)容，具有一定的參考價值，感興趣的小伙伴們可以參考一下

  2018-02-02
• 

  Python matplotlib繪制圖形實例(包括點,曲線,注釋和箭頭)

  這篇文章主要介紹了Python matplotlib繪制圖形實例(包括點,曲線,注釋和箭頭)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

  2020-04-04

最新評論