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 没有多大意义。