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é)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
-
在本教程的開始部分，就已經(jīng)引入了函數(shù)的概念：《永遠(yuǎn)強(qiáng)大的函數(shù)》，之所以那時(shí)候就提到函數(shù)，是因?yàn)槲矣X得函數(shù)之重要，遠(yuǎn)遠(yuǎn)超過一般。這里，重回函數(shù)，一是復(fù)習(xí)，二是要在已經(jīng)學(xué)習(xí)的基礎(chǔ)上，對(duì)函數(shù)有更深刻的理解。
2014-10-10
-
詳解Python如何實(shí)現(xiàn)發(fā)送帶附件的電子郵件
SMTP（Simple Mail Transfer Protocol）即簡(jiǎn)單郵件傳輸協(xié)議,它是一組用于由源地址到目的地址傳送郵件的規(guī)則，由它來控制信件的中轉(zhuǎn)方式。本文將利用SMTP實(shí)現(xiàn)發(fā)送帶附件的電子郵件，感興趣的可以了解一下 2023-04-04
-
今天小編就為大家分享一篇python保存二維數(shù)組到txt文件中的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧 2018-11-11
-
python fabric實(shí)現(xiàn)遠(yuǎn)程操作和部署示例
這篇文章主要介紹了python使用fabric實(shí)現(xiàn)遠(yuǎn)程操作和部署示例,需要的朋友可以參考下 2014-03-03
-
這篇文章主要介紹了python中的hashlib模塊的使用，非常不錯(cuò)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下 2019-04-04
-
Python多進(jìn)程編程multiprocessing代碼實(shí)例
這篇文章主要介紹了Python多進(jìn)程編程multiprocessing代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2020-03-03
-
Python網(wǎng)絡(luò)請(qǐng)求模塊urllib與requests使用介紹
網(wǎng)絡(luò)爬蟲的第一步就是根據(jù)URL，獲取網(wǎng)頁的HTML信息。在Python3中，可以使用urllib和requests進(jìn)行網(wǎng)頁數(shù)據(jù)獲取，這篇文章主要介紹了Python網(wǎng)絡(luò)請(qǐng)求模塊urllib與requests使用 2022-10-10
-
Python中日期和時(shí)間的互相轉(zhuǎn)換操作方法
Python的datetime模塊提供了一套強(qiáng)大而靈活的工具,使我們能夠輕松地在不同的時(shí)間表示形式間相互轉(zhuǎn)換,并進(jìn)行復(fù)雜的時(shí)間計(jì)算,本文通過一個(gè)實(shí)用的例子向大家展示如何在Python中高效地進(jìn)行這些操作,感興趣的朋友一起看看吧 2024-05-05
-
Python爬蟲使用Selenium+PhantomJS抓取Ajax和動(dòng)態(tài)HTML內(nèi)容
這篇文章主要介紹了Python爬蟲使用Selenium+PhantomJS抓取Ajax和動(dòng)態(tài)HTML內(nèi)容，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-02-02
-
Python matplotlib繪制圖形實(shí)例(包括點(diǎn),曲線,注釋和箭頭)
這篇文章主要介紹了Python matplotlib繪制圖形實(shí)例(包括點(diǎn),曲線,注釋和箭頭)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧 2020-04-04
最新評(píng)論
拓?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é)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
- 在本教程的開始部分，就已經(jīng)引入了函數(shù)的概念：《永遠(yuǎn)強(qiáng)大的函數(shù)》，之所以那時(shí)候就提到函數(shù)，是因?yàn)槲矣X得函數(shù)之重要，遠(yuǎn)遠(yuǎn)超過一般。這里，重回函數(shù)，一是復(fù)習(xí)，二是要在已經(jīng)學(xué)習(xí)的基礎(chǔ)上，對(duì)函數(shù)有更深刻的理解。2014-10-10
-
詳解Python如何實(shí)現(xiàn)發(fā)送帶附件的電子郵件
SMTP（Simple Mail Transfer Protocol）即簡(jiǎn)單郵件傳輸協(xié)議,它是一組用于由源地址到目的地址傳送郵件的規(guī)則，由它來控制信件的中轉(zhuǎn)方式。本文將利用SMTP實(shí)現(xiàn)發(fā)送帶附件的電子郵件，感興趣的可以了解一下2023-04-04 - 今天小編就為大家分享一篇python保存二維數(shù)組到txt文件中的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-11-11
-
python fabric實(shí)現(xiàn)遠(yuǎn)程操作和部署示例
這篇文章主要介紹了python使用fabric實(shí)現(xiàn)遠(yuǎn)程操作和部署示例,需要的朋友可以參考下2014-03-03 - 這篇文章主要介紹了python中的hashlib模塊的使用，非常不錯(cuò)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-04-04
-
Python多進(jìn)程編程multiprocessing代碼實(shí)例
這篇文章主要介紹了Python多進(jìn)程編程multiprocessing代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03 -
Python網(wǎng)絡(luò)請(qǐng)求模塊urllib與requests使用介紹
網(wǎng)絡(luò)爬蟲的第一步就是根據(jù)URL，獲取網(wǎng)頁的HTML信息。在Python3中，可以使用urllib和requests進(jìn)行網(wǎng)頁數(shù)據(jù)獲取，這篇文章主要介紹了Python網(wǎng)絡(luò)請(qǐng)求模塊urllib與requests使用2022-10-10 -
Python中日期和時(shí)間的互相轉(zhuǎn)換操作方法
Python的datetime模塊提供了一套強(qiáng)大而靈活的工具,使我們能夠輕松地在不同的時(shí)間表示形式間相互轉(zhuǎn)換,并進(jìn)行復(fù)雜的時(shí)間計(jì)算,本文通過一個(gè)實(shí)用的例子向大家展示如何在Python中高效地進(jìn)行這些操作,感興趣的朋友一起看看吧2024-05-05 -
Python爬蟲使用Selenium+PhantomJS抓取Ajax和動(dòng)態(tài)HTML內(nèi)容
這篇文章主要介紹了Python爬蟲使用Selenium+PhantomJS抓取Ajax和動(dòng)態(tài)HTML內(nèi)容，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02 -
Python matplotlib繪制圖形實(shí)例(包括點(diǎn),曲線,注釋和箭頭)
這篇文章主要介紹了Python matplotlib繪制圖形實(shí)例(包括點(diǎn),曲線,注釋和箭頭)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-04-04