對一個有向無環(huán)圖(Directed Acyclic Graph, DAG)G進(jìn)行拓?fù)渑判虮靠荩瑢中所有頂點排成線性序列坎藐，使得圖中任意一對頂點u、v能颁，若邊(u,v)∈E(G)杂瘸，則在線性序列中u出現(xiàn)在v之前。
隊列Queue--拓?fù)渑判蚴纠?/div>
拓?fù)渑判虻姆椒ǎ?/h4>
1. 在有向圖G中任選一個沒有前驅(qū)(即入度為0)的頂點并輸出它伙菊；
2. 從G中刪除該頂點败玉，并且刪除去從該頂點出發(fā)的全部有向邊；
3. 重復(fù)上述兩步镜硕，直到剩余的網(wǎng)絡(luò)中不再存在有前驅(qū)的頂點為止运翼。
有向無環(huán)圖 demo
Python Demo:
# !/usr/bin/env python
# -- coding: utf-8 --
# @Time : 2017/7/10 11:46
# @Author : Albert·Sun
# @Version : 0.10α
# @Description: (1).用數(shù)組grap存放圖G的連接關(guān)系，grap[i][j]：頂點j指向頂點i,即邊E(j->i),此處邊權(quán)簡化為1; (2).Pyhton中的List結(jié)構(gòu)模擬Queue
def topo(graph):
indegree = []
for i in range(len(graph)):
if sum(graph[i]) is 0:
indegree.append(i)
while len(indegree) > 0:
cur = indegree.pop(0)
print cur+1,
for i in range(len(graph)):
graph[i][cur] = 0
graph[cur][cur] = -1
# print graph
for i in range(len(graph)):
if graph[i][i] is not -1 and graph[i].count(1) is 0:
if indegree.count(i) <= 0:
indegree.append(i)
# print indegree
if __name__ == "__main__":
grap = [[0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
]
topo(grap)
輸出：6 -> 1 -> 2 -> 3 -> 4 -> 5
注：
拓?fù)渑判虻谋举|(zhì)是不斷地輸出入度為0的點兴枯；
該算法可用于判斷圖中是否存在環(huán)血淌。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門栓袖，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人店诗，你說我怎么就攤上這事裹刮。” “怎么了庞瘸？”我有些...
- 文/不壞的土叔 我叫張陵捧弃，是天一觀的道長。 經(jīng)常有香客問我擦囊，道長违霞，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任瞬场，我火速辦了婚禮买鸽，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘贯被。我一直安慰自己眼五，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布彤灶。 她就那樣靜靜地躺著看幼，像睡著了一般。 火紅的嫁衣襯著肌膚如雪幌陕。 梳的紋絲不亂的頭發(fā)上诵姜，一...
- 文/蒼蘭香墨 我猛地睜開眼契邀，長吁一口氣：“原來是場噩夢啊……” “哼摆寄！你這毒婦竟也來了失暴？” 一聲冷哼從身側(cè)響起坯门，我...
- 正文 年R本政府宣布，位于F島的核電站润文，受9級特大地震影響姐呐，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜典蝌，卻給世界環(huán)境...
- 文/蒙蒙 一曙砂、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧骏掀，春花似錦鸠澈、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至侧纯，卻和暖如春新锈，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背眶熬。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)？ 數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合绵疲。 第二章...
- https://zh.visualgo.net/graphds 淺談圖形結(jié)構(gòu)https://zh.visualgo...
- 因為之前就復(fù)習(xí)完數(shù)據(jù)結(jié)構(gòu)了哲鸳，所以為了保持記憶，整理了一份復(fù)習(xí)綱要盔憨，復(fù)習(xí)的時候可以看著綱要想具體內(nèi)容徙菠。 樹 樹的基本...
- 我無聊的時候會刷朋友圈婿奔。昨晚刷朋友圈刷出來一條爆炸性的消息缺狠。室友在和一個我們玩的很好的女生表白。這不是重點萍摊，重點是...
