拓?fù)渑判?/h2>
幾乎在所有的項(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ò)程稱(chēng)為拓?fù)渑判颍╰opological sorting）磕谅。
拓?fù)渑判蛞獫M足如下兩個(gè)條件
- 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次私爷。
- 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑怜庸。
拓?fù)渑判蛩惴?/h2>
任何無(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)的開(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è)回路的話尔崔，那就意味著進(jìn)入了一個(gè)循環(huán)，那么該同學(xué)就畢不了業(yè)了褥民。
因此可以說(shuō)拓?fù)渑判蛩惴ㄊ菫榱俗龀鰸M足制約關(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))
