小編給大家分享一下python如何實(shí)現(xiàn)拓?fù)渑判?，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
拓?fù)渑判?/strong>
幾乎在所有的項(xiàng)目，甚至日常生活，待完成的不同任務(wù)之間通常都會(huì)存在著某些依賴關(guān)系，這些依賴關(guān)系會(huì)為它們的執(zhí)行順序行程表部分約束。對(duì)于這種依賴關(guān)系，很容易將其表示成一個(gè)有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG，無(wú)環(huán)是一個(gè)重要條件），并將尋找其中依賴順序的過(guò)程稱為拓?fù)渑判颍╰opological sorting）。
拓?fù)渑判蛞獫M足如下兩個(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ù)渑判颉?/p>
存在回路，意味著某些活動(dòng)的開始要以其自己的完成作為先決條件，這種現(xiàn)象成為活動(dòng)之間的死鎖。一種常見(jiàn)的頂點(diǎn)活動(dòng)網(wǎng)實(shí)例是大學(xué)課程的先修課程。課程知識(shí)有前后練習(xí)，一門課可能以其他課程的知識(shí)為基礎(chǔ)，學(xué)生想選修這門課程時(shí)，要看是否已修過(guò)所有先修課程。如果存在一個(gè)回路的話，那就意味著進(jìn)入了一個(gè)循環(huán)，那么該同學(xué)就畢不了業(yè)了。
因此可以說(shuō)拓?fù)渑判蛩惴ㄊ菫榱俗龀鰸M足制約關(guān)系的工作安排。
下面我們操作一個(gè)實(shí)例，如下圖是一個(gè)有向無(wú)環(huán)圖：
![python如何實(shí)現(xiàn)拓?fù)渑判?></p><p>用字典表示：G = { 'a':'bce', 'b':'d','c':'d','d':'','e':'cd'}</p><p><strong>代碼實(shí)現(xiàn)：</strong></p><pre>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(](/upload/otherpic4/60126.png)
輸出結(jié)果：
['a', 'e', 'c', 'b', 'd']
圖中有環(huán)的情況：
http://weahome.cn/article/jpojo.html
重慶分公司
重慶分公司
