2

我正在阅读 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 ，我在这里遗漏了一些要点吗？

请举一些例子，谢谢

4

2 回答 2

1

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

于 2015-04-04T09:01:00.557 回答
0

对于任何寻找更快方法的人：有人检查了 Tarjan 与 Johnson 和另一种方法，发现了另一种声称更快但至少更灵活的方法： 链接到文章 和链接到论文（称为“用 Self 枚举图形中的电路和循环-弧和多弧。” KA Hawick 和 HA James）

所有方法都需要以相同语言进行适当的基准测试才能获得可靠的结果。

于 2021-12-18T20:35:41.447 回答