1. 概念及規(guī)則

• 對(duì)一個(gè)有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄?。簡單地說，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?/p>

• 規(guī)則：圖中每個(gè)頂點(diǎn)只出現(xiàn)一次A在B前面，則不存在B在A前面的路徑。(否則就會(huì)形成環(huán))頂點(diǎn)的順序是保證所有指向它的下個(gè)節(jié)點(diǎn)在被指節(jié)點(diǎn)前面例如A—>B—>C那么A一定在B前面，B一定在C前面這個(gè)核心規(guī)則下只要滿足即可，所以拓?fù)渑判蛐蛄胁灰欢ㄎㄒ?/p>

2. 應(yīng)用

• 工廠里產(chǎn)品的生產(chǎn)線上,一個(gè)產(chǎn)品由若干個(gè)零部件組成。零部件生產(chǎn)時(shí),也存在這兩種關(guān)系:先后關(guān)系,即一個(gè)部件必須在完成后才能生產(chǎn)另一個(gè)部件;部件間無先后關(guān)系,即這兩個(gè)部件可以同時(shí)生產(chǎn)

• 大學(xué)里某個(gè)專業(yè)的課程學(xué)習(xí),有些課程是基礎(chǔ)課,它們可獨(dú)立于其他課程,即無前導(dǎo)課程;?有些課程必須在某些基礎(chǔ)課學(xué)完之后才能開始

3. 算法及實(shí)現(xiàn)

• 實(shí)現(xiàn)步驟：維護(hù)一個(gè)入度為0的頂點(diǎn)的集合(棧、隊(duì)列、優(yōu)先隊(duì)列皆可)每次從該集合中取出一個(gè)頂點(diǎn)u(棧頂)遍歷u的鄰接點(diǎn)v,v的入度rd[v]--,如果rd[v]==0,v進(jìn)棧隊(duì)列為空，出棧數(shù)小于n，存在環(huán)

• 時(shí)間復(fù)雜度：由于每個(gè)點(diǎn)入棧出棧一次，每條邊掃描一次，時(shí)間復(fù)雜度為O(n + e)

• 圖示：