问题标签 [cycle-detection]

我正在研究一个hackerrank问题，似乎无论我尝试的解决方案有什么变化，我都无法让循环检测工作。

这是我正在使用的代码

我可以调整解决方案以使其他测试通过，但不能同时通过。在这种情况下，永远不会返回 true，即使它应该返回。我该如何解决这个问题，我做错了什么？

我正在尝试在我创建的链接列表中检测一个循环（我正在练习面试问题）。我理解弗洛伊德的龟兔算法所涉及的逻辑，但该函数总是返回错误......

这是我的链接列表：

这是我的循环检测功能，即使有循环它也会返回 false：

我只是找不到我的功能有什么问题，而且我越想弄清楚我变得越狭隘......任何指导将不胜感激！

前段时间，我将Pollard-Brent 算法的 Python 实现移植到 Clojure。它可以工作，而且工作速度也很快；那不是问题。并且当给定相同的非随机种子值和步进函数时，它会准确地再现 Python 代码的兔子和乌龟位置。

但是当我在研究它时，我不禁注意到乌龟和野兔的移动方式与我预期的基于布伦特论文（或维基百科或任何其他参考选择）。

具体来说，在乌龟传送到兔子的位置后，兔子会向前走distance几步，然后再多走distance几步。此外，在 Brent-Pollard 算法中，中间值也很重要；但是，此代码仅保存了第二个野兔“路径”的步骤。

以下是 Python 代码的第 6-18 行，附有我的评论：

我今天回顾了我的代码，并决定通过模拟一个简化版本来显示索引来确保测试它。这些是当前代码给出的索引：

当前版本：

同时，这是我期望算法做的：

预期输出：

即使将“预期”版本结合到算法中时在 Clojure 中的读取效果更好，但平均需要两倍的时间（这是有道理的，查看索引）。

我的问题：

1. 我的预期输出是布伦特算法的“规范”版本吗？
2. 当前版本仍然是布伦特算法的正确实现吗？
3. 为什么即使野兔路径不包含完全连续的索引，当前版本也能工作？

我是编程和学习算法的新手，当我读到 BFS 可用于循环检测时，我正在研究 BFS。我尝试在具有邻接表表示的无向图 G 上实现相同的功能。我所做的如下：

• 使用队列执行简单的 BFS 遍历，同时维护队列中排队的节点的父节点。

• 如果我遇到一个节点，该节点u的邻居已经被访问但不是其父节点，则意味着图中存在循环。vvvu

伪代码：

上述方法是有效的，除非我在 2 个顶点之间有超过 1 条边，例如在以下情况下，我们在顶点0和之间有 2 条边1：

上图的邻接表是：adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}。在这里我们可以清楚地看到该图包含一个循环（在邻接表表示中，它1在 的邻接表中出现两次并且在 的邻接表中0出现0两次1）但上述算法无法检测到相同的因为当 BFS 到达 vertex 时1， vertex0已经被访问过，但 vertex0也是 vertex 的父级，1所以这个循环不会被检测到。

我的问题是如何修改上述算法来检测这种情况？

编辑：我也在有向图上尝试了相同的逻辑，并且我面临着类似的问题，即当我有一个从顶点到顶点的有向边0和1另一个从顶点1到顶点的有向边时0

我一直在寻找树循环检测，并通过这个 PHP 代码来：

学分：https ://gist.github.com/jmullan/450465/77bdaa2a57e73ecee8ca6d9449aad3f74b379ca5

这完美地检测了树状数据结构中的线性循环，但我无法理解它使用什么算法或代码（数组引用）如何工作。

有人会帮助解释或指出它是什么算法吗？

谢谢。

我正在做一个验证树中循环的程序。小数据没问题，但是当数据增加时，它会停止。请帮帮我。

}

这里是另一部分代码。

Valido 函数帮助我检测给定边缘中的循环。

除了深度优先搜索（DFS）之外，我可以应用联合查找算法来检测有向图中的循环吗？

我知道我们可以将联合查找算法应用于无向图中的检测循环。

我试图了解一些检测图中循环的有效方法的时间复杂度。

此处说明了执行此操作的两种方法。我会假设时间复杂度是根据最坏情况提供的。
第一个是 union-find，据说它的时间复杂度为 O(Vlog E)。
第二种使用基于 DFS 的方法，据说时间复杂度为 O(V+E)。如果我是正确的，这是一个比 O(Vlog E) 更有效的渐进复杂性。基于 DFS 的方法也可以方便地用于有向图和无向图。

我的问题是我看不到如何考虑第二种方法在 O(V+E) 时间内运行，因为 DFS 在 O(V+E) 时间内运行，并且算法会检查与任何已发现节点相邻的节点以进行启动节点。当然，这意味着算法在 O(V ² ) 时间内运行，因为每个发现的节点可能必须遍历多达 V-1 个相邻节点？显然不可能有多个节点需要遍历 n-1 个相邻节点，但据我了解，这仍然是运行时的上限。

希望有人理解我为什么这么认为，并可以帮助我理解为什么复杂性是 O(V+E)。

我知道可以使用 DFS 和 BFS 在直接图中检测循环。我想知道我们是否可以使用Union-Find检测有向图中的循环？

• 如果是，那么如何？和
• 如果我们不能，那为什么？

我最近了解到：

（通常）内存中的堆总是向上增长

参考-> https://unix.stackexchange.com/questions/466443/do-memory-mapping-segment-and-heap-grow-until-they-meet-each-other
我大部分都不懂，但是当我搜索堆是否在内存中向上增长时，我得到了类似的结果。

考虑到 c/c++ 中的上述事实，我编写了一个检查循环检测的函数，如果指向结构的遍历指针指向temp的内存地址小于链表中前一个节点的内存地址，则该函数返回 TRUE 以进行循环检测.

不幸的是，下面的代码在hackerrank上没有给出预期的结果，我想知道为什么。代码是：

我已经检查了堆中的内存分配是否向下if( x <= temp )（降序）的条件，因为内存分配是特定于设备/编译器的，但这也不起作用。我想知道为什么这段代码不起作用以及这段代码存在哪些概念错误。