Kosaraju 的算法陈述如下:
#Input is graph G
1-define G_rev (links in reversed order)
2-Find the finishing times for G_rev using DFS
3-Run DFS for G in sequence based on finishing time
运行时间为 O(n+m)，其中 n 是顶点数，m 是边数。 如果我有一个完整的图G(所有节点都相连)，边的数量是m = n*n。 这个完全图 G 的运行时间是多少？当我查看 (1) 中的 DFS 代码时，我将从节点 1(外循环)开始，我将访问并完成所有其他节点。外循环将遍历所有其他节点并发现它们已完成并跳过它们。 这同样适用于(2)。看来我不会访问 n*n 边。 如果 G 是完备的，则只有一个 SCC(全图)，运行时间为 O(n+m) 且 m < n*n 。这是对的吗？
最佳答案
这是正确的。你的运行时间是 O(n+m) = O(n²)。
请注意，如果您事先知道您的图表是完整的，那么在其上运行 SCC 就没有多大意义。
关于algorithm - 使用 DFS Kosaraju 查找 SCC 的最差运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19475592/