Topological翻成中文是拓墣的意思，若不是數學系的好像翻譯後也還是不會懂。

直接來看範例還是最快吧：

符合上圖graph的topological sort會是[0, 2, 1, 3, 5, 4, 7, 6]，或者[2, 0, 3, 5, 1, 4, 6, 7]，也還有其他答案，只要不違反edge的先後方向順序都可以是topological sort。

可以用擋修的科目來想像，要先修微積分1→微積分2→工程數學1，最後才能修工程數學2，所以就如同點0, 1, 4, 7這樣，在topological sort的結果中，這四個的前後順序就一定是這樣。

那該利用什麼演算法可以找出graph的topological sort呢？直覺上會想到用BFS：

但如同上圖所示，若我們加上了點8，並讓他的edge指向點7，這時用BFS就會破壞了點7在點2與點0了順序性。

聰明的前人發現其實BFS postorder的結果很能符合topological sort的順序性，只不過其結果是倒反的。那又如何呢？最後再反過來就好了嘛！

最後得到[7, 4, 1, 3, 0, 6, 5, 2]，倒反過來是[2, 5, 6, 0, 3, 1, 4, 7]，符合topological sort！

最後老師提供了另一個角度來看topological sort，若我們把topological sort的結果排成一維的，然後再把graph的edge畫上來，會發現只要是topological sort，畫出來的edge一定都會是由左往右，不會有反方向的edge出現：

一個需要注意的特點，Topological Sort只會出現在DAG(Directed Acyclic Graph)：

首先directed應該不用多做解釋了，acyclic是說不可以有edge連回先前的點造成cycle，有了cycle就不可能符合topological的定義。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License