用于 SCC 最坏情况分析的 Tarjan 算法
Tarjan Algorithm for SCC worst case analysis
我正在阅读 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 之后，现在根据我的理解，所有其他顶点将简单地 return 因为它们的索引已经存在定义并且 k 个顶点应该再花费 k 时间，所以总结起来应该是 2k 次而不是 k**2 ，我在这里遗漏了一些点吗？
请提供一些示例，谢谢
"Tarjan's algorithm" 在这种情况下不是强连通分量的算法。这是他用于枚举基本电路的算法。然而，在 the original paper 中，这种方法被认为具有紧迫的最坏情况 O((V + E) * (C + 1)) 时间。有趣的是，Tarjan 用来证明这个界限（找到两个电路之间的 O(V + E) 时间）的论点在 Johnson 的论文中突然改变了（找到两个电路之间的 O(V * E) 时间）。我对这两种算法都不熟悉，所以我不能说哪个是正确的。快速搜索似乎认为 Johnson 的算法渐近速度更快（即使这两种方法都声称具有相同的时间复杂度），但我在任何地方都找不到反驳 Tarjan 论文中时间复杂度的来源。
对于正在寻找更快方法的任何人：有人将 Tarjan 与 Johnson 和另一种方法进行了比较，发现了另一种声称速度更快但至少更灵活的方法：
link to writeup
和 link to paper（称为“具有自弧和多弧的图中的枚举电路和环路。”作者：K.A。Hawick 和 H.A。James）
所有方法都需要使用相同的语言进行适当的基准测试才能获得可靠的结果。
我正在阅读 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 之后，现在根据我的理解，所有其他顶点将简单地 return 因为它们的索引已经存在定义并且 k 个顶点应该再花费 k 时间，所以总结起来应该是 2k 次而不是 k**2 ，我在这里遗漏了一些点吗？
请提供一些示例，谢谢
"Tarjan's algorithm" 在这种情况下不是强连通分量的算法。这是他用于枚举基本电路的算法。然而，在 the original paper 中，这种方法被认为具有紧迫的最坏情况 O((V + E) * (C + 1)) 时间。有趣的是，Tarjan 用来证明这个界限（找到两个电路之间的 O(V + E) 时间）的论点在 Johnson 的论文中突然改变了（找到两个电路之间的 O(V * E) 时间）。我对这两种算法都不熟悉，所以我不能说哪个是正确的。快速搜索似乎认为 Johnson 的算法渐近速度更快（即使这两种方法都声称具有相同的时间复杂度），但我在任何地方都找不到反驳 Tarjan 论文中时间复杂度的来源。
对于正在寻找更快方法的任何人：有人将 Tarjan 与 Johnson 和另一种方法进行了比较，发现了另一种声称速度更快但至少更灵活的方法： link to writeup 和 link to paper（称为“具有自弧和多弧的图中的枚举电路和环路。”作者：K.A。Hawick 和 H.A。James）
所有方法都需要使用相同的语言进行适当的基准测试才能获得可靠的结果。