algorithm - 使用 DFS Kosaraju 查找 SCC 的最差运行时间

Question

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 。这是对的吗？

Answer 1

这是正确的。你的运行时间是 O(n+m) = O(n²)。

请注意，如果您事先知道您的图表是完整的，那么在其上运行 SCC 就没有多大意义。