尋找強連接組件？

Question

我的書定義了一種在線性時間內查找有向圖的強連通分量的方法。此外，還有其他一些用於查找強連通組件的算法（即Tarjan算法）也能夠在線性時間內找到這些組件。

但是，所有這些算法都要求圖的頂點按減去後值（頂點剩下的時間）排序。常見的排序算法如Mergesort需要O（n log n）時間。

因此如何做這些算法設法完成線性時間定位的強連接組件，如果後值需要O排序頂點列表（N log n）的時間？

Answer 1

由於「時間」（測量後值的類型）作爲時間的函數（深度優先搜索程序執行的步驟的數量）是單調非降低的，所以可以將每個節點附加到在遍歷離開它後立即列表。在遍歷結束時，列表按排序順序排列。另外，由於後值是多項式上界的整數，所以在一些機器模型上，可以使用例如線性時間對它們進行排序。基數排序。