0. 概述

學(xué)習(xí)下拓?fù)渑判?/p>

1. 零入度算法

1. 1 拓?fù)渑判?/h3>

首先理解下拓?fù)渑判?/p>

其實(shí)老師經(jīng)常干這事，如編講義，將已經(jīng)知道的知識(shí)點(diǎn)串起來變成講課序列。那怎么串起來呢？將知識(shí)點(diǎn)列出，將它們之間的相互關(guān)系描述下。要講priority queue那上一講需要講什么內(nèi)容，要講hashing需要講哪些內(nèi)容，需要羅列出來。但是講課不可能像分支一樣平行一分為二裂開，最終都會(huì)變成下面這樣平坦的線性序列。

（續(xù)）一個(gè)好的安排是什么呢？每當(dāng)講到一個(gè)知識(shí)點(diǎn)時(shí)，它所依賴的知識(shí)點(diǎn)都應(yīng)該在此前依然講過，這樣就會(huì)變成一個(gè)線性序列。將原來圖中所有的點(diǎn)整理成這樣一個(gè)線性次序，前面點(diǎn)與后面點(diǎn)的邊次序都是前指向后，沒有后指向前，這就是對(duì)原圖的拓?fù)渑判颉?/p>

1. 2 算法

• 如果真有這么一個(gè)圖，怎么排呢？
  
  因?yàn)檫@個(gè)圖有依賴關(guān)系，所以是不折不扣的有向圖，但有意思的是這里不能有環(huán)，如果有環(huán)路就有問題。

首先需要找到零入度的點(diǎn)——無任何依賴，在dag圖中必然有這么一個(gè)點(diǎn)，由于DAG子圖亦為DAG，于是可以利用減而治之思想，將這個(gè)零入度的點(diǎn)抹掉，接著找下一個(gè)零入度點(diǎn)。

• 那么這個(gè)算法如何實(shí)現(xiàn)？

圖中已經(jīng)有零入度的點(diǎn)A或B，任取一個(gè)，這里取A，放入隊(duì)列中，等價(jià)將A點(diǎn)及其邊從圖中刪除。由于DAG的子圖亦是DAG，所以還會(huì)有零入度的點(diǎn)，將B點(diǎn)放入隊(duì)列中，然后依次類推，當(dāng)所有的點(diǎn)都放入隊(duì)列后，隊(duì)列中的節(jié)點(diǎn)順序就是拓?fù)渑判颉?/p>

但這個(gè)方法并不好，實(shí)現(xiàn)起來比較麻煩，需要每次去找那個(gè)零入度的點(diǎn)，而且刪除點(diǎn)及其邊的時(shí)候還要更新相應(yīng)信息，可能會(huì)對(duì)圖產(chǎn)生傷害，那怎么做呢？看下下面的零出度算法

2. 零出度算法

2.1 算法

說服下自己，DAG既有零入度點(diǎn)也有零出度點(diǎn)，這個(gè)很重要，為什么這么講，因?yàn)橹暗腄FS（深度優(yōu)先搜索）可以幫我們實(shí)現(xiàn)這個(gè)方法。

這樣要做的事就比較簡單，不需要零入度算法那這樣改改度數(shù)等等。之前已經(jīng)造出DFS算法，這樣就可以搭DFS便車實(shí)現(xiàn)零出度算法。

如何實(shí)現(xiàn)呢？

2.2 實(shí)現(xiàn)

這里引入一個(gè)棧，排序結(jié)果將以逆序打印出來。隨便找一個(gè)點(diǎn)，這里首先訪問頂點(diǎn)V，將頂點(diǎn)V狀態(tài)初始值設(shè)置為DISCOVERED，接著枚舉V的所有鄰居，視u的狀態(tài)，分別處理，后續(xù)會(huì)做分析。訪問所有鄰居后，將頂點(diǎn)V的狀態(tài)設(shè)置為VISITED，然后頂點(diǎn)V入棧。

接著還有頂點(diǎn)V的鄰居處理方法還未做交代，怎么處理呢？

1. 若頂點(diǎn)U的狀態(tài)為UNDISCOVERED，更新頂點(diǎn)U的父親為V，邊的狀態(tài)為TREE，作遞歸調(diào)用，從頂點(diǎn)u處深入。
2. 頂點(diǎn)U的狀態(tài)為DISCOVERED，一旦發(fā)現(xiàn)后向邊，即圖非DAG圖，無拓?fù)渑判?#xff0c;則退出而不再深入。
3. 頂點(diǎn)U的狀態(tài)為VISITED，更新下頂點(diǎn)狀態(tài)。

2.3. 復(fù)雜度

這里僅額外引入的棧，規(guī)模不超過頂點(diǎn)總數(shù)O(n)。總體而言，空間復(fù)雜度與基本的深度優(yōu)先搜索算法同樣，仍為O(n + e)。該算法的遞歸跟蹤過程與標(biāo)準(zhǔn)DFS搜索完全一致，且各遞歸實(shí)例自身的執(zhí)行時(shí)間依然保持為O(1)，故總體運(yùn)行時(shí)間仍為O(n + e)。