Topological Sort

Topological Sort為depth-first search的一種應用，
可以排序出做某些事的先後順序。

要使用topological sort，
G必須是dag (directed acyclic graph)才行。

演算法很簡單，
首先使用DFS去計算每個vertex的結束時間，
接著每當一個vertex結束時，就把它插入linked list的前端。

Introduction to Algorithms Fig. 22.7

如上圖(a)，
以shirt為起點，用DFS去計算每個vertex的finish時間。

shirt->tie->jacket，此時jacket結束，
因此把jacket插入linked list的前端。
接著依序以tie->belt->shirt的順序結束，
因此以這個順序將這些nodes插入linked list的前端。
到目前為止，linked list的內容即為：shirt->belt->tie->jacket。

圖(b)是以shirt為起點的其中一種order，
它並不是唯一解。
topological sort會因起點不同、以及DFS實作方式的不同，
而產生不同的結果，
但都算是正確的一種order。