问题标签 [tarjans-algorithm]

我正在尝试对图中的一组节点执行 tarjans 算法，我可以成功找到强连接组件，但是根节点或低值节点始终处于关闭状态，即使对于只有 1 个元素的 SCC，根节点也不匹配元素 例如：

其中顶部是低值节点，底部是构成 SCC 的 1 元素

我目前拥有的代码在这里

我怀疑问题在于设置低值。我认为不需要任何其他类信息，因为从图中检索边没有问题

在Tarjan 算法中，有两个索引数组，一个按节点被发现的顺序连续编号。另一个表示从v到v的子树可以到达的最小索引，这是算法的伪代码

但我认为可以删除低数组，算法更改为

我对小图做了一些测试，结果与标准 tarjan 相同。但我不确定它是否能成功地在各种图中找到强连通分量。这个算法是正确的还是只能通过弱测试用例。

谁能解释我为什么我们要说 eq1: low[a]=min(low[a],discovery[b]) 而不是说 eq2: low[a] = min(low[a],low[b])当有从 a 到 b 的后边时

我已经尝试了很多案例，并且在所有情况下 eq2 在 tarjan 算法中都可以正常工作

如果存在 eq1 和 eq2 工作方式不同的示例，请在答案中提及

我正在尝试使用 GFG- tarjan算法示例中给出的这个示例来了解 tarjan 算法中使用的低时间 。根据 GFG，lowtime 的定义是 lowtime 是指示每个节点可以从该节点直接到达的最顶层祖先或通过该节点的子树可到达的最顶层祖先（具有最小可能的发现时间值）的时间节点。现在在给定的示例中，B、C 和 D 的低值为 1，E、F、G 的低值为 3，H、I、J 的低值为 6。

但我的疑问是为什么 E,F,G 的低值不是 1，我的意思是我们可以通过路径从 E 到达 A - E->F->G->C->A OR E->F- >G->C->D->A，所以 E 的最高祖先应该是 A 而不是 C，同样对于 F 和 G，它们的低值也应该是 1。

我知道我在理解这个算法的某个地方是错误的，但是我在 youtube 上观看了很多视频并且浏览了很多网站，但我仍然无法理解这一点。如果有人对 tarjan 算法有有用的链接，那么请在这里分享并澄清这个例子，即 E 的低时间如何不是 1。

这是 GFG 上 tarjan 算法的链接 - Tarjan Algorithm GFG

我有以下实现来在图中找到切边/桥：

该实现适用于大多数测试用例，除了一个。一个测试用例有 1000 个节点和约 56k 条边。我正在尝试解决这个问题 - https://leetcode.com/problems/critical-connections-in-a-network/

如何验证是错误的代码还是测试用例？

如果您已经知道 Tarjan 算法，请查看代码。

我最近遇到了在无向图中查找所有循环的算法，当我看到它们运行线性时间时感到困惑（示例），使用其中一个来查找汉密尔顿循环似乎很容易（对于我们找到的每个循环，只需检查如果它是多项式时间内的n个节点，例如包含所有节点），但汉密尔顿问题是一个已知的NP完全问题，所以我必须遗漏一些东西......我在这里遗漏了什么？

谢谢！