问题标签 [tarjans-algorithm]

我正在尝试实现 Tarjan 的强连接组件 (SCC) 的迭代版本，为方便起见，在此处复制（来源：http ://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ）。

我的迭代版本使用以下 Node 结构。

这是我为迭代版本所做的：

我的迭代版本运行并给我与递归版本相同的输出。问题是迭代版本比较慢，我不知道为什么。谁能给我一些关于我的实施的见解？有没有更好的方法来迭代地实现递归算法？

根据维基百科，我用 Python 实现了 Tarjan 的强连接组件算法，但它不起作用。该算法很短，我找不到任何区别，所以我不知道为什么它不起作用。我试图检查原始文件，但找不到它。

这是代码。

如果您愿意，可以直观地检查图表。如您所见，这是对维基百科中伪代码的非常正向的翻译。但是，这是输出：

应该只有一个强连通分量，而不是三个。我希望这个问题在各个方面都是正确的，如果不是，我很抱歉。无论如何，非常感谢你。

这是 tarjan 循环检测的有效 C# 实现。

该算法可在此处找到： http ://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

注意 DepGraph 只是一个顶点列表。并且 Vertex 有一个代表边缘的其他 Vertex 列表。index 和 lowlink 也被初始化为 -1

编辑：这是有效的......我只是误解了结果。

我正在尝试从wikipedia运行 Tarjan java 实现。我的最终目标是在特定点注入一些 println，这将使我能够进一步理解代码。

到目前为止我做了什么

• 我复制粘贴了这3个源代码

a)Tarjan 源代码 b)Edge 源代码 c)节点源代码 j 在同一文件夹下的 3 个单独文件中。

• 我能够运行一个 helloworld 示例（不幸的是，我的 Java 背景几乎为零，上次我编写 Java 代码是为了家庭作业，多年前）。

我面临的具体问题是什么， 我得到了 3 个错误：

对应的行：9、28、14是这些

附加解释 我没有把我得到的错误作为标题，因为我不知道这是一个实际错误还是我做错了什么，也许我必须包含文件（比如在 php..don't知道）。我发布这个是希望让它运行起来很简单，因为代码已经存在。

谢谢大家！

我已经尝试从 Wikipedia 学习 Tarjan 的算法 3 个小时了，但我就是无法理解它。:(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

为什么它是 DFS 树的子树？（实际上 DFS 产生了一片森林？o_O）为什么v.lowlink=v.index暗示那v是一个根？

有人可以向我解释一下/给出这个算法背后的直觉或动机吗？

我正在阅读以下链接中的代码http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 我一直碰到“低链接”这个词，我没有知道这意味着什么。我知道这是一个相当无聊的问题，但有人可以向我解释一下吗？谢谢。

我正在阅读Tarjan 关于 scc 的论文。

在论文中，给定顶点的低链接定义为：

LOWLINK (v) 是与 v 位于同一组件中的最小顶点，可以通过遍历零个或多个树弧后跟最多一个叶子或交叉链接来到达。

我无法通过交叉链接边缘从给定 scc 中的两个顶点的路径想出任何情况，因为整个 scc 应该位于由 dfs 搜索派生的一棵树中。谁能解释一下？

我继续在 Scala 中实现了Tarjan 的 SCC 算法的教科书版本。但是，我不喜欢这段代码——它是非常命令式/程序化的，有很多变异状态和簿记索引。该算法是否有更“功能”的版本？我相信命令式算法版本隐藏了算法背后的核心思想，与函数式版本不同。我发现其他人在使用这个特定算法时遇到了同样的问题，但我无法将他的 Clojure 代码翻译成惯用的 Scala。

注意：如果有人想尝试，我有一个很好的设置，可以生成随机图并测试你的 SCC 算法与运行 Floyd-Warshall

我是一名在算法方面学习信息学奥林匹克的大四学生，这是我在 stackoverflow 上的第一个问题。

在 tarjan 的 dfs 搜索中得到lowlink(u)：

low[u]=min(low[u],low[v])（v 未访问）

或者

low[u]=min(low[u],dfn[v])（v仍在堆栈中）

我的问题是，在第二种情况下将dfn[v]替换为low[v]是否仍然可以？我知道这是不正确的，但我找不到反例。谁能帮忙解释一下？

谢谢：）

假设在一个圆圈图中有许多具有某个值的顶点。

在使用Tarjan找出这些SCC之后，我想将每个整个SCC变成两个顶点（不是一个），一个在这个SCC的这些顶点中具有最高值，另一个具有最低值。

让连接到这个SCC的那些顶点指向具有最低值的顶点，并且让从SCC指向的顶点指向具有最高值的顶点。

也就是说，像 1(4) -> 2(3) <-> 3(5) -> 5(1) <-> 4(6) -> 1(4)，括号中的权重，是一个圆圈。我想把它翻译成类似的东西1(4) -> 2(3) -> 3(5) -> 4(1) -> 5(6) , 1(4) -> 4(1)

但我不知道如何实现这一点，请帮忙。

我正在使用 C 和邻接列表来存储图形。

对不起英语不好，我希望它足够清楚，可以理解。