问题标签 [tarjans-algorithm]

我正在尝试使用 Tarjan 的算法确定有向图中的循环，该算法在他 1972 年 9 月的研究论文“有向图的基本电路的枚举”中提出。

我使用 Python 对算法进行编码，并使用邻接列表来跟踪节点之间的关系。

所以在下面的“G”中，节点 0 指向节点 1，节点 1 指向节点 4、6、7……等等。

Tarjan 算法检测以下循环：

[2, 4]

[2、4、3、6、5]

[2、4、3、7、5]

[2, 6, 5]

[2、6、5、3、4]

[2, 7, 5]

[2、7、5、3、4]

[3, 7, 5]

我也完成了 Tiernan 的算法，它（正确地）找到了 2 个额外的循环：

[3,4]

[3,6,5]

如果能帮助我找出 Tarjan 跳过这两个周期的原因，我将不胜感激。也许我的代码有问题？

a我正在尝试在树上实现一些算法，其中一个步骤是找到节点处理的发现和完成时间（类似于 Tarjan 的 SSC），这是通过全局时间状态完成的。我在 Haskell 中使用由列表和计时器组成的 State monad 做到了这一点。然而，在较大的树上，这部分代码会出现堆栈溢出和性能下降的问题，您能提出一些改进的建议吗？

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

请举一些例子，谢谢

我正在研究Tarjan 的强连接组件算法，它的工作方式对我来说很清楚。无论如何，有一句我不明白：

我用星号标记了这条线。为什么遇到后边时要取节点的发现索引/时间

而不是仅仅抓住它的组件价值？

我想不出这会成为问题的情况。

有人可以启发我吗？编辑：我怀疑这只是一个语义要求，即低链接被定义为从只有一个 back-edge的节点可到达的最早祖先，但这只是一个疯狂的猜测。

我最近学习了线性时间算法来计算图表中的关节点。我的实现在 Online Judge Test Data 上正确运行，因此代码没有问题。但是，我似乎很难在 DFS 运行中如何出现多个相同的关节点。让我解释

我有一个列表，如果遇到关节点，则存储它们。现在，当我最后打印列表时，我得到了正确的关节点，但是作为关节点的几个顶点不止一次出现在列表中。根据我的说法，这不应该发生，因为我们只遇到每个顶点一次。那么为什么我会在列表中重复输入？为了解决这个问题，我在原始代码中使用了一个 HashSet 来存储它们，最后只打印了给出正确答案的内容。这是我的问题代码。该算法主要基于维基百科上的伪代码：https ://en.wikipedia.org/wiki/Biconnected_component

这是我在 C++ 中的实现代码：

带有输入和输出的代码：http: //ideone.com/u5dYOy（看看 2 是怎么来的三次？）

为什么会这样？我在算法中遗漏了什么吗？我相信我对算法的运行有一个很好的了解。任何帮助表示赞赏。谢谢

我一直在研究 SCC 和有关它们的算法，并且我看到人们几乎总是提到 Kosaraju 的算法找到 SCC 并以（反向）拓扑排序对其进行排序。

我的问题是：Tarjan 的算法不是也找到了（反向）拓扑排序吗？我发现它没有被提及（至少从我读过的地方，维基百科除外）。

我一直在考虑它并且完全有道理。当在某个节点 u 上调用 tarjans_dfs 时，所有可以从 u 到达的 SCC 都将在 u 的 SCC 之前找到。我错了吗？

维基百科说它确实找到了它：

“虽然每个强连接组件中节点的顺序没有什么特别之处，但该算法的一个有用特性是，在其任何继任者之前不会识别强连接组件。因此，强连接组件的顺序是识别构成了由强连接组件形成的 DAG 的反向拓扑排序。”

是我的想法，还是说 Kosaraju 的算法找到拓扑顺序比 Tarjan 的算法也能找到拓扑顺序更广为人知？

我一直在研究Tarjan 的关节点查找算法，它说如果根节点有 1 个以上的子节点，它就是一个关节点。但是如果图是强连接的，即使它有超过 1 个子节点，根节点也不应该是关节点。有人可以解释一下吗？

每当我在任何图上运行 tarjans 算法时，它总是声称有一个循环，例如这个图：

A -> B -> C

算法会告诉我有一个循环：

当有循环时，例如：

A -> B -> C -> A

输出很奇怪：

这是我的实现：

但我不确定我哪里出错了。我已经按照近 1:1 的比例关注了关于 tarjans 算法的维基百科文章和伪代码。我对图论和图​​算法很陌生，所以我无法理解这里的错误是什么。

修复 tarjan()

我读了一篇关于 Tarjan 算法的文章， 博客。在这篇文章中，作者提出了一个问题：

情况二，我们可以用 low[v] 代替 disc[v] 吗？. 答案是否定的。如果您能想到为什么答案是否定的，那么您可能理解了 Low 和 Disc 的概念。

我不知道为什么。当我在wiki中阅读类似的文章时，我发现代码可以是这样的：

我想知道为什么作者说答案是否定的。谢谢回答我的问题。祝你有美好的一天。

城市通过电话线连接并进行通信。我想摧毁所有的城市，但又不想过早地惊动另一个城市，所以我在摧毁城镇之前断开了电线。我不想断开用作两个城市之间桥梁的城镇。

如果我没记错的话，它是无向图。但我不明白如何检查我可以删除哪些城市，哪些不能。我查看了 Tarjan 的算法，但我不明白。

这是测试输入：

输出可以是这样的：