判断图有无环_浅谈什么是图拓扑排序
1 引言
??在工程實(shí)踐中,一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成。這些子項(xiàng)目間往往有兩種關(guān)系:
??(1) 先后關(guān)系，即必須在某個(gè)項(xiàng)完成后才能開始實(shí)施另一個(gè)子項(xiàng)目。
??(2) 子項(xiàng)目間無關(guān)系，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行,互不影響。
??例如：在工廠里產(chǎn)品的生產(chǎn)線上，一個(gè)產(chǎn)品由若干個(gè)零部件組成。零部件生產(chǎn)時(shí)，也存在這兩種關(guān)系:
??(1)先后關(guān)系，即一個(gè)部件必須在完成后才能生產(chǎn)另一個(gè)部件;
??(2)部件間無先后關(guān)系，即這兩個(gè)部件可以同時(shí)生產(chǎn)。
??那么如何合理的分配資源才能保證工程能夠按時(shí)完成呢？將任務(wù)作為圖的頂點(diǎn)，將任務(wù)之間的依賴關(guān)系作為圖的邊，這樣就可以將實(shí)際問題抽象為數(shù)據(jù)結(jié)構(gòu)圖論中的典型問題——圖的拓?fù)渑判颉?/p>
2 重要概念
??有向無環(huán)圖(Directed Acyclic Graph, DAG)是有向圖的一種，字面意思的理解就是圖中沒有環(huán)。常常被用來表示事件之間的驅(qū)動(dòng)依賴關(guān)系，管理任務(wù)之間的調(diào)度。AOV網(wǎng)：在每一個(gè)工程中，可以將工程分為若干個(gè)子工程，這些子工程稱為活動(dòng)。如果用圖中的頂點(diǎn)表示活動(dòng)，以有向圖的弧表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為AOV網(wǎng)，即頂點(diǎn)表示活動(dòng)的網(wǎng)。在AOV網(wǎng)中，如果從頂點(diǎn)vi到頂點(diǎn)j之間存在一條路徑，則頂點(diǎn)vi是頂點(diǎn)vj的前驅(qū)，頂點(diǎn)vj是頂點(diǎn)vi的后繼。活動(dòng)中的制約關(guān)系可以通過AOV網(wǎng)中的表示。 在AOV網(wǎng)中，不允許出現(xiàn)環(huán)，如果出現(xiàn)環(huán)就表示某個(gè)活動(dòng)是自己的先決條件。因此需要對(duì)AOV網(wǎng)判斷是否存在環(huán)，可以利用有向圖的拓?fù)渑判蜻M(jìn)行判斷。拓?fù)湫蛄?#xff1a;設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1,v2,…,vn,滿足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在vj之前，則我們稱這樣的頂點(diǎn)序列為一個(gè)拓?fù)湫蛄小?strong>拓?fù)渑判?#xff1a;拓?fù)渑判蚴菍?duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程。
3 拓?fù)渑判?/span>
??拓?fù)渑判?Topological Sorting)是一個(gè)有向無環(huán)圖(DAG, Directed Acyclic Graph)的所有頂點(diǎn)的線性序列。且該序列必須滿足下面兩個(gè)條件：
??(1)每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
??(2)若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，那么在序列中頂點(diǎn) A 出現(xiàn)在頂點(diǎn) B 的前面。
??注：有向無環(huán)圖(DAG)才有拓?fù)渑判?#xff0c;非DAG圖沒有拓?fù)渑判蛞徽f。
4 入度表法
??入度表法是根據(jù)頂點(diǎn)的入度來判斷是否存在依賴關(guān)系。若頂點(diǎn)入度不為0。則必然此頂點(diǎn)的事件有前驅(qū)依賴事件，因此每次選取入度為0的頂點(diǎn)輸出，則符合拓?fù)渑判虻男再|(zhì)。
4.1 算法流程
(1)從圖中選擇一個(gè)入度為0的頂點(diǎn)，輸出該頂點(diǎn)。
(2)從圖中刪除該節(jié)點(diǎn)及其所有出邊(即與之鄰接的所有頂點(diǎn)入度-1)
(3)反復(fù)執(zhí)行這兩個(gè)步驟，直至所有節(jié)點(diǎn)都輸出，即整個(gè)拓?fù)渑判蛲瓿?#xff1b;或者直至剩下的圖中再?zèng)]有入度為0的節(jié)點(diǎn)，這就說明此圖中有回路，不可能進(jìn)行拓?fù)渑判颉?/p>
4.2 實(shí)例圖解
例如：圖4.2.1所示的有向無環(huán)圖，采用入度表的方法獲取拓?fù)渑判蜻^程。
4.2.1(1)選擇圖中入度為0的頂點(diǎn)1，輸出頂點(diǎn)1。刪除頂點(diǎn)1，并刪除以頂點(diǎn)1為尾的邊。刪除后圖為：
(2)繼續(xù)選擇入度為0的頂點(diǎn)。現(xiàn)在，圖中入度為0的頂點(diǎn)有2和4，這里我們選擇頂點(diǎn)2，輸出頂點(diǎn)2。刪除頂點(diǎn)2，并刪除以頂點(diǎn)2為尾的邊。刪除后圖為：
(3)選擇入度為0的頂點(diǎn)4，輸出頂點(diǎn)4.刪除頂點(diǎn)4，并刪除以頂點(diǎn)4為尾的邊。刪除后圖為：
(4)選擇入度為0的頂點(diǎn)3，輸出頂點(diǎn)3.刪除頂點(diǎn)3，并刪除以頂點(diǎn)3為尾的邊。刪除后圖為：
(5)最后剩余頂點(diǎn)5，輸出頂點(diǎn)5，拓?fù)渑判蜻^程結(jié)束。最終的輸出結(jié)果為：
4.3 性能分析
??算法時(shí)間復(fù)雜度分析：統(tǒng)計(jì)所有節(jié)點(diǎn)入度的時(shí)間復(fù)雜性為(VE)；接下來刪邊花費(fèi)的時(shí)間也是(VE)，總花費(fèi)時(shí)間為O(VE)。若使用隊(duì)列保存入度為0的頂點(diǎn)，則可以將這個(gè)算法復(fù)雜度將為O(V+E)。
5 DFS方法
??深度優(yōu)先搜索過程中，當(dāng)?shù)竭_(dá)出度為0的頂點(diǎn)時(shí)，需要進(jìn)行回退。在執(zhí)行回退時(shí)記錄出度為0的頂點(diǎn)，將其入棧。則最終出棧順序的逆序即為拓?fù)渑判蛐蛄小?/p>
5.1 算法流程
(1)對(duì)圖執(zhí)行深度優(yōu)先搜索。
(2)在執(zhí)行深度優(yōu)先搜索時(shí)，若某個(gè)頂點(diǎn)不能繼續(xù)前進(jìn)，即頂點(diǎn)的出度為0，則將此頂點(diǎn)入棧。
(3)最后得到棧中順序的逆序即為拓?fù)渑判蝽樞颉?/p>
5.2 實(shí)例圖解
例如圖5.2.1所示的有向無環(huán)圖，采用DFS的方法獲取拓?fù)渑判蜻^程。
5.2.1(1)選擇起點(diǎn)為頂點(diǎn)1,，開始執(zhí)行深度優(yōu)先搜索。順序?yàn)?->2->3->5。
(2)深度優(yōu)先搜索到達(dá)頂點(diǎn)5時(shí)，頂點(diǎn)5出度為0。將頂點(diǎn)5入棧。
(3)深度優(yōu)先搜索執(zhí)行回退，回退至頂點(diǎn)3。此時(shí)頂點(diǎn)3的出度為0，將頂點(diǎn)3入棧。
(4)回退至頂點(diǎn)2，頂點(diǎn)2出度為0，頂點(diǎn)2入棧。
(5)回退至頂點(diǎn)1，頂點(diǎn)1可以前進(jìn)位置為頂點(diǎn)4，順序?yàn)?->4。
(6)頂點(diǎn)4出度為0，頂點(diǎn)4入棧。
(7)回退至頂點(diǎn)1，頂點(diǎn)1出度為0，頂點(diǎn)1入棧。
(8)棧的逆序?yàn)?->4->2->3->5。此順序?yàn)橥負(fù)渑判蚪Y(jié)果。
5.3 性能分析
??時(shí)間復(fù)雜度分析：首先深度優(yōu)先搜索的時(shí)間復(fù)雜度為O(V+E)，而每次只需將完成訪問的頂點(diǎn)存入數(shù)組中，需要O(1)，因而總復(fù)雜度為O(V+E)。
推薦閱讀
拜托，面試官別問我「布隆」了
有點(diǎn)難度，幾道和「滑動(dòng)窗口」有關(guān)的算法面試題
數(shù)據(jù)結(jié)構(gòu)與算法：三十張圖弄懂「圖的兩種遍歷方式」
昨天，終于拿到了騰訊 offer
幾道和「二叉樹」有關(guān)的算法面試題
幾道和散列(哈希)表有關(guān)的面試題
一道看完答案你會(huì)覺得很沙雕的「動(dòng)態(tài)規(guī)劃算法題」
幾道和「堆棧、隊(duì)列」有關(guān)的面試算法題
鏈表算法面試問題？看我就夠了！
我就知道你在看！ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)總結(jié)
以上是生活随笔為你收集整理的判断图有无环_浅谈什么是图拓扑排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 十字链表存储稀疏矩阵
- 下一篇： HashMap和ConcurrentHa