问题标签 [cycle-detection]

有没有办法使用不超过两个指针找出链接列表中循环的开始？ 我不想访问每个节点并将其标记为已看到并报告第一个节点已被看到。有没有其他方法可以做到这一点？

假设我想通过替换字典中的占位符来扩展字符串。替换字符串还可以包含占位符：

只要没有圆形替换模式，例如"c" => "#b#". 然后程序将陷入无限循环，直到内存耗尽。

有没有一种简单的方法来检测这种模式？我正在寻找一种解决方案，其中替换之间的距离可以任意长，例如。a->b->c->d->f->a
理想情况下，解决方案也将发生在循环中，而不是单独分析。

我在检查我的邻接列表是否有循环时遇到了一些问题。我想创建一个函数来检查我的邻接列表是否存在至少一个循环。

基于我的程序。首先，我必须输入Root Node，然后是节点的数量，图中的节点，边的数量，以及表示边的邻接列表。邻接表中的每个条目都包含一对节点。

样本输入：

上面的示例输入有一个循环： [ A --> B --> C --> A ]我想输出它是否有一个循环。

到目前为止，这是我的程序：

我上面的程序还没有检查周期的功能，而且我想实现根节点的东西.. 如果有人可以改进我上面的程序，请回答我并给我一些我可以依赖的代码。谢谢！（我是初学者！）

我已经通过http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/的实现尝试了 Tarjan 的循环检测算法。下图用于测试：
ab
ac
ba
bc
cd
da
作为输出，我得到以下结果： Set 0: [c, b, a, d]

我的问题是我需要所有周期，所以我在这个结果中缺少 Sets [a,b] 和 [a,c,d]。您现在是否有办法修改实现以获取所有周期？或者这个问题是否存在另一种算法？

谢谢！

那么这个问题更多的是关于一种有效的算法而不是实现，所以我不会发布代码。（不会真正帮助您理解问题）

向您介绍这个问题：我正在开发一个程序来计算 automovilistics 崩溃报告。它为您提供了一系列“方程式”（Eq从现在开始，Eqs 表示复数），您可以在其中输入数据并通常得到 n 个结果。

例如：您选择覆盖的空间（x），并输入时间（t），加速度（a）和初始速度（v），然后x =（a * t）+（（a * t ^ 2）/ 2）。问题是这个 Eqs 在一个对象内部，其中包含比 vars 和 ecuation 本身更多的东西，让我们称之为Bo（我正在谈论的 busssines 对象。

所以 BO 相当大（并且需要），除其他外，1 Bo 可以有 N 个 Eqs，并且不止一个结果，此外，每个 Eq 都可以将值范围作为输入，这会让你康复。 . （假设您只能在 2 个变量上使用范围，实际上这不受限制）因此您将获得每个结果的结果表（一些 Bos 有 4 个不同的结果）。范围的步数有上限，第一个范围为 20 个，第二个范围为 10 个。（在一个有 4 个结果的 Bo 中，将映射到 1 个 Bo 的 800 个结果）。

顺便说一句，我必须将这个 Bos 及其各自的结果存储（保存在文件中），并且 Var 输入每次都无法在运行时计算它们（我可以只保存 ecuation 和 var 输入并计算每次我的结果需要他们），因为博斯可以改变他们的评价，而用户需要保留以前的结果，不要问..

此外，您可以将 Bo 的一个结果导入另一个 Bo 的 Eq 输入。所以在前面的例子中（我们称之为 Bo1）加速度可能来自另一个计算它的 Bo (Bo2)，并采用其他参数来计算它，如果你改变 Bo2 的输入，结果会改变，所以至少 1 Bo1 的 var 会发生变化，从而使 Bo1 的结果发生变化。这可以级联（B2 从 B3 导入等等）。一个 Bo 可以从其他 N 个 Bos 导入其所有 N 个变量。

我不能使用指针或引用类型（也许可以使用引用类型，无论如何这将是很多工作，必须处理来自不同用户的先前保存的数据，以及对象缺少引用等）。

我决定只使用数组的集合，在每个数组中存储，{Id_of_Bo_Exporting, Id_Bo_importing,Id_Variable_of_Bo_Importing,..(ohters ids to map the especific result exporting)} 数组是 int 的（对于前 2 个来说很长）。

我真的不喜欢它，但代码工作得很好。（感谢阅读）问题即将到来，我保证。

问题是，我必须检查循环进口，如果 B3 从 B2 进口和 B2 从 B1 进口，我不应该允许从 B3（或 B2）进口 Bo1。这将导致无限循环，（我可以停止循环，但从数学角度来看，这不是允许导入的逻辑）。

和进口清单，最终可能真的很长，

我想到了一个 ArrayList< ArrayList< long>> 所以每次我添加一个导入时，我都会在这个我不喜欢的“东西”上添加 Id。(arraylist的arraylist)

每个长数组将在第一个位置具有“Bo id 标头”，并且每次 Bo 导入时，新 Id 都会添加到其列表中，并且每个其他 Bo 都会导入 Bo（进行导入的那个）。

因此，如果我的用户尝试从 B1 制作 B9，该方法将检测到，B1 被添加到自己的列表中并且不允许。

实施很容易。（让我们使用 java，不，我使用的是 .net，我自己没有启动项目）

例子 {{}}

B1 从 B2 导入：{ {B1,B2} }

B1 从 B6 导入：{{B1,B2, B6 }}

B2 从 B4 导入： {{B1,B2,B6, B4 }, {B2,B4} }

B4 从 B9 导入： {{B1,B2,B3,B4, B9 },{B2,B4, B9 }, {B4,B9 }}

B3 从 B10 导入： {{B1,B2,B3,B4,B9, B10 },{B2,B4,B9},{B4,B9}, {B3,B10} }

每个长数组将在第一个位置具有“Bo id 标头”，并且每次 Bo 导入时，新 Id 都会添加到其列表中，并且每个其他 Bo 都会导入 Bo（进行导入的那个）。

因此，如果我的用户尝试从 B1 制作 B9，该方法将检测到，B1 被添加到自己的列表中并且不允许。

实施很容易。（让我们使用 java，不，我使用的是 .net，我自己没有启动项目）

现在的问题（使用 ListSet 或其他什么）你能想出一种更有效的方法来做到这一点吗？两个列表（导入和 iL 可以很快变大，具体取决于用户）。字幕是速度。

我有一个有向图，即 nx n 阶矩阵。
我需要找到其中存在的所有循环以及循环中涉及的顶点。

这是一个例子：

输出应类似于：

给定一个大小矩阵，m X n在行或列中没有重复值，是否有一种有效的检测周期的方法？

例如，这是一个示例矩阵：

3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5

它至少有一个大小为 3 的置换循环：

3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5

第 2、4 和 5 行中的值 3、6 和 8 形成一个循环。

这个问题与Kakuro谜题有关。与解决它们无关，而是尝试检测特定网格的任何布局是否使其不适合。任何类型的循环都会使该特定布局无效 - 因为两种布局的行和列的总和是相同的。

我的理解是龟兔式算法适用于迭代序列，也就是说，对于任何 x，succ(x) = x0。

我想实现一种算法，可以检测确定性和非确定性无限重复序列中的循环。

序列可能具有不重复的前缀子序列，例如在序列中1666666...，具有前缀1和重复模式6。

该算法将返回序列中最长的重复模式。的重复模式001100110011...将是0011，的重复模式22583575837583758...将是58357。

我的想法是从那里以某种方式生成可能的最长模式长度的猜测，但我无法按顺序排列。

我在 Saurabh Kr Vats 在http://www.careercup.com/question?id=14990323提出的解决方案中遇到了这个问题

他说：

我在网上搜索并达到了循环检测。当我们到达一个循环的开始/结束并尝试去一个不相邻的元素时，我可以看到形成 rho 形状。然而，我不理解序列的表示或其用法。

如果有人可以举例说明，那就太好了。

最近我参加了一次采访，遇到了以下我无法弄清楚的问题。

问题一：

根据我阅读的证明，乌龟一次移动 1 步，而野兔一次移动 2 步。我明白这一点，因为野兔的移动速度是乌龟的两倍，他们会在某个时候相遇。他们不能有任何随机值，比如 2 和 3 或 3 和 5 或 2 和 4。如果是这样，他们会弄清楚循环吗？选择 Tortoise 和 Hare 值的条件是什么？我们可以选择任何随机值吗？

问题2：

龟兔赛跑有没有条件进入循环？假设 Tortoise 和 Hare 是否具有以下值，分别为 2 和 4。而链表就像

如果乌龟在节点 3 处进入循环，而野兔在节点 2 处进入循环，那么它们在循环内永远不会相遇。那么龟兔赛跑有没有条件进入循环呢？

是否应该选择任何限制值以使它们彼此相遇？