问题标签 [tarjans-algorithm]

我正在尝试将tarjan 算法的递归 python 代码转换为 scala，尤其是这部分：

我知道 scala here 或here中有 tarjan 算法，但它没有返回好的结果并从 python 翻译它帮助我理解它。

这是我所拥有的：

我知道这根本不是 scala 方式（而且不干净......），但我计划在第一个版本工作时慢慢将其更改为更实用的样式。

现在，我得到了这个错误：

在这条线上

我认为它来自这条线，但我不确定：

但是调试它真的很难，因为我不能只打印我的错误......

谢谢 ！

Tarjan 的强连通分量算法只能找到图中的基本循环或所有循环？

我有这个带有 Matlab 的 tarjan 程序的代码源，当我运行 prog 时出现这个错误，我该如何修复它

问题在于星星之间的cc

我正在 Matlab 中实现 Tarjan 算法。
我使用此源代码来确定强连接组件。
这是我得到的结果，我怎样才能用 Matlab（一个确定彩色强连通分量的图）查看结果？
什么是适当的命令？

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

http://en.algoritmy.net/article/44220/Tarjans-algorithm

我无法在我的 Ruby 版本的 Tarjan 强连接组件算法中找出这个错误。我得到了 Kosaraju–Sharir 算法，我的 Ruby 中的 Tarjan 算法适用于一些图。但它没有连接应该连接的2个组件---“10”和“11,12,9”

输入文件是这个有向图：http ://algs4.cs.princeton.edu/42directed/tinyDG.txt

在这个尝试制作单个组件的最终循环中，它以“10”（堆栈上的最后一项）开始，但当前顶点（“父级”）也是“10”！这使得循环切断“10”作为一个单独的组件。为什么栈上的最新项与父节点相同？在我们收集 ["12", "11", "9"...then "10"] 之后，我希望“10”只会出现在组件的末尾。因为“10”首先出现，而不是最后出现，所以我们遇到了这个问题。我如何解决它？

我的红宝石代码：

我正在使用 Tarjan 算法实现强连接组件。我将输入作为节点和边的链接列表。但是，gcc 编译器每次在递归函数中都会给出分段错误（在 while 循环中，我正在检查顶点的相邻节点）。

知道这段代码有什么问题吗？

当我在解析树中属性的循环依赖的上下文中遇到以下行时，我正在研究“编译器：Aho、Ullman、Sethi 和 Lam 的原则、技术和工具”中的语法定向定义：

在计算上很难确定给定 SDD 可能必须转换的任何解析树中是否存在任何循环。（部分：5.1.2）

同样在http://cs.nyu.edu/courses/fall12/CSCI-GA.2130-001/lecture8.pdf中提到

检测周期具有指数时间复杂度

但是有 Tarjan 的强连通分量算法，可以在 O(E+V) 中找到循环。那么为什么上述来源与此相矛盾呢？

谁能告诉我我错过了什么？

我在一个家庭作业问题上遇到了一些麻烦，涉及在提供的图表上使用 Tarjan 算法来找到该图表的特定 SCC。虽然（根据我的教授）我通过使用此处找到的伪代码算法找到了正确的 SCC ，但我的 SCC 中的一些节点与该 SCC 的根节点不共享相同的最低链接号。

从我可以从伪代码中收集到的信息来看，这是因为如果一个未引用的节点i（它是当前递归调用算法的输入节点）与一个已经访问过的节点（不是根节点）有i + 1一条弧线，然后算法设置is LL = MIN(i.LowestLink, (i + 1).index)，并且(i + 1).index可能不再等于它自己的最低链接值。

例如（这类似于我要解决的问题中的图的一部分）：如果我们在 中有节点，在 中有N = {a, b, c, d}弧E = {a ⇒ c, c ⇒ b, c ⇒ d, b ⇒ a, d ⇒ b}，并且我们从中启动算法的根节点是a，那么：

1.1) 我们设置a.index = 1（使用 1 而不是 0）, a.LL = 1, 并压入a堆栈；a有一个单一的弧线c，所以我们检查c; 发现它未被发现，我们将算法称为c.

2.1) 我们设置c.index = 2, c.LL = 2, 并c入栈；c有两条弧线，一条到b，一条到d。假设我们的 for 循环b首先检查；b未被发现，因此我们将算法称为b。

3.1) 我们设置b.index = 3, b.LL = 3, 并压入b堆栈；b有一个弧到a; 检查a我们发现它已经在堆栈上，所以（通过上面链接的伪代码）我们设置b.LL = MIN(b.LL, a.index) = a.index = 1; b没有更多的弧，所以我们退出我们的 for 循环，并检查 if b.LL = b.index，它没有，所以我们结束这个算法的实例。

2.2) 现在递归调用b已经结束，我们设置c.LL = MIN(c.LL, b.LL) = b.LL = 1. c仍有从c到d剩余的弧；检查d我们发现它是未定义的，所以我们调用算法 on d。

4.1)d.index设置为 4，d.LL设置为 4，然后我们压入d堆栈。从到d有一条弧，所以我们检查; 我们发现它已经在堆栈中，所以我们设置. 没有更多的弧线，所以我们退出我们的 for 循环并检查 if ; 它没有，所以我们结束这个算法的实例。dbbbd.LL = MIN(d.LL, b.index) = b.index = 3dd.LL = d.index

2.3) 随着递归调用d结束，我们再次设置c.LL = MIN(c.LL, d.LL) = c.LL = 1. c没有更多的弧，所以我们结束了我们的 for 循环。我们检查是否c.LL = c.index；它没有，所以我们结束这个算法的实例。

1.2) 随着递归调用c结束，我们设置a.LL = MIN(a.LL, c.LL) = 1. a没有更多的弧线，所以我们结束了我们的 for 循环。我们检查是否a.LL = a.index；它们是相等的，所以我们找到了这个 SCC 的根节点；我们创建一个新的 SCC，并将堆栈中的每个项目弹出到这个 SCC 中，直到我们a在堆栈中找到（也进入这个 SCC）。

在这些步骤之后，图中的所有节点都被发现了，因此与其他节点一起运行算法最初什么都不做，我们有一个SCC = {a, b, c, d}. 但是，d.LL = 3这不等于其余节点的最低链接（全为 1）。

我在这里做错了吗？或者在这种情况下是否有可能在其节点之间拥有一个具有不同最低链接的 SCC？

这个问题与最近在这里提出的问题相关但不同。

我刚刚阅读了Wikipedia 伪代码。

我显然不能正确理解它，因为我有两个非常基本的问题：

1. 当我们说 时if (w is in S)，这不是 O(N) 或至少 O(logN) 复杂度的操作，因为元素应按其索引排序吗？我们必须为从根节点访问的每个新节点执行此操作，因此总体复杂性不是O(NlogN)。此外，S 是一个堆栈，所以从概念上讲，只有顶部元素应该是可访问的，我们如何在其中实现搜索？在这里，二叉搜索树不应该是更好的数据结构吗？

2. 在这部分：

   else if (w is in S) then
   v.lowlink := min(v.lowlink, w.index)

w.index使用和不使用是否有特定原因w.lowlink？使用的好处w.lowlink是它可以回答上一个问题（链接问题）。对于LLsSCC 中的所有节点，将保证所有节点都相同。

我有一个特殊的问题，即有向图的每个顶点恰好有四个向外指向的路径（它们可以指向同一个顶点）。

一开始，我只有起始顶点，我使用 DFS 发现/枚举所有顶点和边。

然后我可以使用 Tarjan 算法之类的东西将图形分解为强连接的组件。

我的问题是，有没有比发现图形然后应用算法更有效的方法。例如，有没有办法将这两个部分结合起来以提高效率？