algorithm - 用于 SCC 最坏情况分析的 Tarjan 算法

Question

我正在阅读 Donal B.Johnson 关于在有向图中查找所有基本电路的论文，http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

在这篇论文中，他提到 Tarjan 算法的最坏情况是 O(V*E (c+1))虽然在其他地方都显示为 O(V+E)，但 Johnson 论文用几个例子来证明这一点，如论文中的图 1 和图 2。

图 2 的示例非常相似，在 O(k) 时间内找到第一个循环 1...k 之后，现在根据我的理解，所有其他顶点将简单地返回，因为它们的索引已经定义并且应该需要另一个k 个顶点的 k 次，所以总结起来应该是 2k 次而不是 k**2 ，我在这里遗漏了一些点吗？

请举例说明，谢谢

Answer 1

“Tarjan 算法”在这种情况下不是强连通分量的算法。这是他用于枚举基本电路的算法。然而，在 the original paper ，此方法被认为具有紧迫的最坏情况 O((V + E) * (C + 1)) 时间。有趣的是，Tarjan 用来证明这个界限(找到两个电路之间的 O(V + E) 时间)的论点在 Johnson 的论文中突然改变了(找到两个电路之间的 O(V * E) 时间)。我对这两种算法都不熟悉，所以我不能说哪个是正确的。快速搜索似乎认为 Johnson 的算法渐近更快(尽管这两种方法都声称具有相同的时间复杂度)，但我找不到任何可以反驳 Tarjan 论文中时间复杂度的来源。