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

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

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

拓?fù)渑判?/strong>

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

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

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

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

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

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

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

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

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

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

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

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

def toposort(graph):
 in_degrees = dict((u,0) for u in graph) #初始化所有頂點(diǎn)入度為0
 vertex_num = len(in_degrees)
 for u in graph:
  for v in graph[u]:
   in_degrees[v] += 1  #計(jì)算每個(gè)頂點(diǎn)的入度
 Q = [u for u in in_degrees if in_degrees[u] == 0] # 篩選入度為0的頂點(diǎn)
 Seq = []
 while Q:
  u = Q.pop()  #默認(rèn)從最后一個(gè)刪除
  Seq.append(u)
  for v in graph[u]:
   in_degrees[v] -= 1  #移除其所有指向
   if in_degrees[v] == 0:
    Q.append(v)   #再次篩選入度為0的頂點(diǎn)
 if len(Seq) == vertex_num:  #如果循環(huán)結(jié)束后存在非0入度的頂點(diǎn)說明圖中有環(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é)

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

您可能感興趣的文章:

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

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

相關(guān)文章

• 

  Python中優(yōu)雅使用assert斷言的方法實(shí)例

  我們?cè)陂_發(fā)一個(gè)程序時(shí)候,與其讓它運(yùn)行時(shí)崩潰,不如在它出現(xiàn)錯(cuò)誤條件時(shí)就崩潰(返回錯(cuò)誤),這時(shí)候斷言assert就顯得非常有用,這篇文章主要給大家介紹了關(guān)于Python中優(yōu)雅使用assert斷言的相關(guān)資料,需要的朋友可以參考下

  2021-09-09
• 

  Python實(shí)現(xiàn)刪除windows下的長(zhǎng)路徑文件

  這篇文章主要為大家詳細(xì)介紹一下如何利用Python語(yǔ)言實(shí)現(xiàn)刪除windows下的長(zhǎng)路徑文件功能，文中的示例代碼講解詳細(xì)，具有一定參考借鑒價(jià)值，感興趣的可以了解一下

  2022-07-07
• 

  Python模擬實(shí)現(xiàn)高斯分布擬合

  當(dāng)我們繪制一個(gè)數(shù)據(jù)集（如直方圖）時(shí),圖表的形狀就是我們所說的分布,最常見的連續(xù)值形狀是鐘形曲線,也稱為高斯分布或正態(tài)分布,下面我們就來利用Python模擬實(shí)現(xiàn)一下高斯分布吧

  2023-12-12
• 

  python list語(yǔ)法學(xué)習(xí)（帶例子）

  python list語(yǔ)法學(xué)習(xí)

  2013-11-11
• 

  Python中利用算法優(yōu)化性能的技巧分享

  這篇文章主要為大家詳細(xì)介紹了Python中12個(gè)可以利用算法優(yōu)化性能的技巧,文中的示例代碼簡(jiǎn)潔易懂,具有一定的借鑒價(jià)值,有需要的小伙伴可以了解下

  2025-04-04
• 

  詳解python with 上下文管理器

  這篇文章主要介紹了python with和上下文管理器的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下

  2020-09-09
• 

  在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息

  今天小編就為大家分享一篇在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

  2020-02-02
• 

  python繪制封閉多邊形教程

  今天小編就為大家分享一篇python繪制封閉多邊形教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

  2020-02-02
• 

  如何使用Python提取Chrome瀏覽器保存的密碼

  今天小編教大家怎么用Python提取Chrome瀏覽器保存的密碼,在這需要導(dǎo)入一些必要模塊定義一些有用的函數(shù)來幫助我們?cè)谥骱瘮?shù)中調(diào)用，具體實(shí)例代碼跟隨小編一起學(xué)習(xí)下吧

  2021-06-06
• 

  Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析

  這篇文章主要介紹了Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

  2020-08-08

最新評(píng)論