所謂的拓?fù)渑判虻暮诵木褪窃谝粋€有向圖中，如果存在邊u 到v， 則排序后u一定要在v的前面。

其基本的排序思路如下所示：

?示意圖如上所示。我們對這個圖進(jìn)行拓?fù)渑判颉Ｎ覀兊幕舅悸窞?#xff1a;

TopSort(G)

- 找到一個入度為0 的點(diǎn)(沒有前節(jié)點(diǎn))，輸出

- 刪除與該點(diǎn)所有相連的邊

-重復(fù)上述步驟知道所有點(diǎn)被explored

其執(zhí)行步驟為

?實(shí)際上我們也可以在拓?fù)渑判蛑忻恳徊秸页龆葹?的點(diǎn)，即沒有后繼節(jié)點(diǎn)輸出。不過最后要將得到的序列反序。

?出度為0的節(jié)點(diǎn)一般叫做沉沒節(jié)點(diǎn)(sink node)。下一篇文章我們會講如何使用DFS來完成拓?fù)渑判颉?有向無環(huán)圖才能進(jìn)行拓?fù)渑判颉Ｓ协h(huán)就不知道誰該排在前面了。

注：文中兩幅示意圖來自博客：

https://blog.csdn.net/lisonglisonglisong/article/details/45543451

總結(jié)

以上是生活随笔為你收集整理的拓扑排序- 基本思路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。