拓?fù)渑判蛑饕鉀Q的問(wèn)題是給一個(gè)圖的所有節(jié)點(diǎn)排序。

一、什么是拓?fù)渑判?/p>

在圖論中，拓?fù)渑判颍═opological Sorting）是一個(gè)有向無(wú)環(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 的前面。

有向無(wú)環(huán)圖（DAG）才有拓?fù)渑判?，非DAG圖沒(méi)有拓?fù)渑判蛞徽f(shuō)。

例如，下面這個(gè)圖：

它是一個(gè) DAG 圖，那么如何寫出它的拓?fù)渑判蚰?？這里說(shuō)一種比較常用的方法：

從 DAG 圖中選擇一個(gè) 沒(méi)有前驅(qū)（即入度為0）的頂點(diǎn)并輸出。

從圖中刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊。

重復(fù) 1 和 2 直到當(dāng)前的 DAG 圖為空或當(dāng)前圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止。后一種情況說(shuō)明有向圖中必然存在環(huán)。

于是，得到拓?fù)渑判蚝蟮慕Y(jié)果是 { 1, 2, 4, 3, 5 }。

通常，一個(gè)有向無(wú)環(huán)圖可以有一個(gè)或多個(gè)拓?fù)渑判蛐蛄小?/p>

二、現(xiàn)實(shí)案例

看了上面關(guān)于拓?fù)渑判虻母拍钊绻€覺(jué)得十分抽象的話，那么不妨考慮一個(gè)非常非常經(jīng)典的例子 —— 選課。

假設(shè)我非常想學(xué)習(xí)一門《jsp 入門》的課程，但是在修這么課程之前，我們必須要學(xué)習(xí)一些基礎(chǔ)課程，比如《JAVA 語(yǔ)言程序設(shè)計(jì)》，《HTML 指南》等等。那么這個(gè)制定選修課程順序的過(guò)程，實(shí)際上就是一個(gè)拓?fù)渑判虻倪^(guò)程，每門課程相當(dāng)于有向圖中的一個(gè)頂點(diǎn)，而連接頂點(diǎn)之間的有向邊就是課程學(xué)習(xí)的先后關(guān)系。

只不過(guò)這個(gè)過(guò)程不是那么復(fù)雜，從而很自然的在我們的大腦中完成了。將這個(gè)過(guò)程以算法的形式描述出來(lái)的結(jié)果，就是拓?fù)渑判颉?/p>

可以看到，上圖中的學(xué)習(xí)順序，就是拓?fù)湫蛄校洳恢挂粋€(gè)結(jié)果。

拓?fù)渑判蛩惴ㄔ诠こ虒W(xué)中十分重要。

節(jié)點(diǎn)成環(huán)的圖，無(wú)法被拓?fù)渑判颍驗(yàn)檫@在工程上本身沒(méi)有意義，比如 A——>B——>C——>A，那么這個(gè)工程永遠(yuǎn)無(wú)法被開始。

三、算法實(shí)現(xiàn)

拓?fù)渑判虻淖顑?yōu)時(shí)間復(fù)雜度是 O (m+n), 其中 m 和 n 是 DAG 圖中節(jié)點(diǎn)數(shù)和邊數(shù)。因?yàn)橥負(fù)渑判蛑辽僖獙?duì) DAG 圖的節(jié)點(diǎn)和邊進(jìn)行一次完整的遍歷。

拓?fù)渑判虻淖顑?yōu)空間復(fù)雜度是 O (m+n), 其中 m 和 n 是 DAG 圖中節(jié)點(diǎn)數(shù)和邊數(shù)。我們一般使用鄰接表來(lái)存儲(chǔ) DAG 圖，因此空間復(fù)雜度是 O (m+n)。