找到强连接的部件？

Question

我的书定义了一种在线性时间内找到有向图强连通分量的方法。此外，其他几种寻找强连通分量的算法(即Tarjan算法)也能在线性时间内找到强连通分量。

然而，所有这些算法都要求对图的顶点进行降后值排序(顶点离开的时间)。常用的排序算法，如Mergesort取O(n log )时间。

因此，如果通过 post 值对顶点列表排序需要O(n log )时间，那么这些算法如何能够在线性时间内完成强连通分量的定位？

Answer 1

由于" time“(测量post值的类型)是一个时间的函数(深度优先搜索程序执行的步骤数)，所以在遍历结束后立即将每个节点追加到列表中就足够了。在遍历结束时，列表按排序顺序排列。

或者，由于post值是多项式上有界的整数，所以在某些机器模型上，可以使用例如基数排序在线性时间对它们进行排序。