python實(shí)現(xiàn)拓?fù)渑判虻幕窘坛?/h1>
更新時(shí)間：2018年03月11日 09:51:50 作者：趙潔鈺Amy
拓?fù)渑判蚴菍?duì)有向無(wú)環(huán)圖的一種排序，發(fā)現(xiàn)自己并沒(méi)有真的理解拓?fù)渑判颍俅螌W(xué)習(xí)了下，所以下面這篇文章主要給大家介紹了關(guān)于python實(shí)現(xiàn)拓?fù)渑判虻幕窘坛蹋闹型ㄟ^(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下，
拓?fù)渑判?/strong>
幾乎在所有的項(xiàng)目，甚至日常生活，待完成的不同任務(wù)之間通常都會(huì)存在著某些依賴(lài)關(guān)系，這些依賴(lài)關(guān)系會(huì)為它們的執(zhí)行順序行程表部分約束。對(duì)于這種依賴(lài)關(guān)系，很容易將其表示成一個(gè)有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG，無(wú)環(huán)是一個(gè)重要條件），并將尋找其中依賴(lài)順序的過(guò)程稱(chēng)為拓?fù)渑判颍╰opological sorting）。
拓?fù)渑判蛞獫M(mǎn)足如下兩個(gè)條件
- 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
- 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。
拓?fù)渑判蛩惴?/strong>
任何無(wú)回路的頂點(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)，就說(shuō)明N中有回路，不存在拓?fù)渑判颉?br />
存在回路，意味著某些活動(dòng)的開(kāi)始要以其自己的完成作為先決條件，這種現(xiàn)象成為活動(dòng)之間的死鎖。一種常見(jiàn)的頂點(diǎn)活動(dòng)網(wǎng)實(shí)例是大學(xué)課程的先修課程。課程知識(shí)有前后練習(xí)，一門(mén)課可能以其他課程的知識(shí)為基礎(chǔ)，學(xué)生想選修這門(mén)課程時(shí)，要看是否已修過(guò)所有先修課程。如果存在一個(gè)回路的話(huà)，那就意味著進(jìn)入了一個(gè)循環(huán)，那么該同學(xué)就畢不了業(yè)了。
因此可以說(shuō)拓?fù)渑判蛩惴ㄊ菫榱俗龀鰸M(mǎn)足制約關(guān)系的工作安排。
下面我們操作一個(gè)實(shí)例，如下圖是一個(gè)有向無(wú)環(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)說(shuō)明圖中有環(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à)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
-
Python中優(yōu)雅使用assert斷言的方法實(shí)例
我們?cè)陂_(kāi)發(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
-
當(dāng)我們繪制一個(gè)數(shù)據(jù)集（如直方圖）時(shí),圖表的形狀就是我們所說(shuō)的分布,最常見(jiàn)的連續(xù)值形狀是鐘形曲線(xiàn),也稱(chēng)為高斯分布或正態(tài)分布,下面我們就來(lái)利用Python模擬實(shí)現(xiàn)一下高斯分布吧 2023-12-12
-
python list語(yǔ)法學(xué)習(xí)（帶例子）
python list語(yǔ)法學(xué)習(xí) 2013-11-11
-
這篇文章主要為大家詳細(xì)介紹了Python中12個(gè)可以利用算法優(yōu)化性能的技巧,文中的示例代碼簡(jiǎn)潔易懂,具有一定的借鑒價(jià)值,有需要的小伙伴可以了解下 2025-04-04
-
這篇文章主要介紹了python with和上下文管理器的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下 2020-09-09
-
在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息
今天小編就為大家分享一篇在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧 2020-02-02
-
今天小編就為大家分享一篇python繪制封閉多邊形教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧 2020-02-02
-
今天小編教大家怎么用Python提取Chrome瀏覽器保存的密碼,在這需要導(dǎo)入一些必要模塊定義一些有用的函數(shù)來(lái)幫助我們?cè)谥骱瘮?shù)中調(diào)用，具體實(shí)例代碼跟隨小編一起學(xué)習(xí)下吧 2021-06-06
-
Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析
這篇文章主要介紹了Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2020-08-08
最新評(píng)論
拓?fù)渑判?/strong>
幾乎在所有的項(xiàng)目，甚至日常生活，待完成的不同任務(wù)之間通常都會(huì)存在著某些依賴(lài)關(guān)系，這些依賴(lài)關(guān)系會(huì)為它們的執(zhí)行順序行程表部分約束。對(duì)于這種依賴(lài)關(guān)系，很容易將其表示成一個(gè)有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG，無(wú)環(huán)是一個(gè)重要條件），并將尋找其中依賴(lài)順序的過(guò)程稱(chēng)為拓?fù)渑判颍╰opological sorting）。
拓?fù)渑判蛞獫M(mǎn)足如下兩個(gè)條件
- 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
- 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。
拓?fù)渑判蛩惴?/strong>
任何無(wú)回路的頂點(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)，就說(shuō)明N中有回路，不存在拓?fù)渑判颉?br />
存在回路，意味著某些活動(dòng)的開(kāi)始要以其自己的完成作為先決條件，這種現(xiàn)象成為活動(dòng)之間的死鎖。一種常見(jiàn)的頂點(diǎn)活動(dòng)網(wǎng)實(shí)例是大學(xué)課程的先修課程。課程知識(shí)有前后練習(xí)，一門(mén)課可能以其他課程的知識(shí)為基礎(chǔ)，學(xué)生想選修這門(mén)課程時(shí)，要看是否已修過(guò)所有先修課程。如果存在一個(gè)回路的話(huà)，那就意味著進(jìn)入了一個(gè)循環(huán)，那么該同學(xué)就畢不了業(yè)了。
因此可以說(shuō)拓?fù)渑判蛩惴ㄊ菫榱俗龀鰸M(mǎn)足制約關(guān)系的工作安排。
下面我們操作一個(gè)實(shí)例，如下圖是一個(gè)有向無(wú)環(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)說(shuō)明圖中有環(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à)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
-
Python中優(yōu)雅使用assert斷言的方法實(shí)例
我們?cè)陂_(kāi)發(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 - 當(dāng)我們繪制一個(gè)數(shù)據(jù)集（如直方圖）時(shí),圖表的形狀就是我們所說(shuō)的分布,最常見(jiàn)的連續(xù)值形狀是鐘形曲線(xiàn),也稱(chēng)為高斯分布或正態(tài)分布,下面我們就來(lái)利用Python模擬實(shí)現(xiàn)一下高斯分布吧2023-12-12
-
python list語(yǔ)法學(xué)習(xí)（帶例子）
python list語(yǔ)法學(xué)習(xí)2013-11-11 - 這篇文章主要為大家詳細(xì)介紹了Python中12個(gè)可以利用算法優(yōu)化性能的技巧,文中的示例代碼簡(jiǎn)潔易懂,具有一定的借鑒價(jià)值,有需要的小伙伴可以了解下2025-04-04
- 這篇文章主要介紹了python with和上下文管理器的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-09-09
-
在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息
今天小編就為大家分享一篇在tensorflow中實(shí)現(xiàn)屏蔽輸出的log信息，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02 - 今天小編就為大家分享一篇python繪制封閉多邊形教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
- 今天小編教大家怎么用Python提取Chrome瀏覽器保存的密碼,在這需要導(dǎo)入一些必要模塊定義一些有用的函數(shù)來(lái)幫助我們?cè)谥骱瘮?shù)中調(diào)用，具體實(shí)例代碼跟隨小編一起學(xué)習(xí)下吧2021-06-06
-
Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析
這篇文章主要介紹了Python3 ffmpeg視頻轉(zhuǎn)換工具使用方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08