问题标签 [cycle-detection]

所以我知道弗洛伊德的循环检测算法，但是在研究这个问题时，我想出了另一个解决它的想法。

如果我们可以在遍历链表时将每个节点的“ nextpointer ”存储在向量/列表中，如果任何元素的频率大于1，则计数。如果向量/列表中的任何值出现不止一次，则基本上意味着单个节点已被指向两次（或更多），因此它变成了一个循环。

我无法在 Python 3 中编写相同的代码。如果你们能帮助我，我将不胜感激。谢谢。

对于 Scheme 编程语言，我没有发现任何与此相关的问题，所以我希望这不是重复的。

在涉足解释器时，我遇到了一个奇怪的情况：

显然，在将列表对象更改为现在是循环的后，list?将返回#f.

为什么 Scheme 不将循环列表视为列表？我想这与 list 的正式定义有关，但是 Scheme 是如何制定这样的定义的呢？另外，list?就拥有检测循环列表的属性而言，它是如何实现的？

给定一个类似于链表的数据结构，其中一个指针指向下一个节点，另一个指针指向任何随机节点，我必须打印该结构具有的所有唯一循环。下面是这个数据结构的一个例子：

这里的唯一循环是 (1,2,1), (2,3,4,5,2), (1,3,5,2,1), (3,4,3) 等等，但是 (1,2 ,3,4,5,2,1), (1,2,3,4,3) 不是循环。打印所有这些独特循环的算法应该是什么？

我正在解决一个问题，以确定图形是否包含循环。我使用着色方法解决了它（在访问的数组中我将标记，如果它从未访问过，则为 0，如果已访问过，如果已访问过，则为 2）为此我编写了代码：

现在，我在想，是否有办法编写已检测到的循环。我知道大多数人会说 DFS 和回溯，它非常直观。但想知道我该如何实现它。

问题

编写一个 JAVA 程序来计算无向图中的循环数。

我的做法：

我尝试使用深度优先搜索来解决这个问题。

我在网上找到了一个程序，可以计算无向连通图中长度为 n 的循环。

代码来自：https ://www.geeksforgeeks.org/cycles-of-length-n-in-an-undirected-and-connected-graph/

我通过创建函数 count() 对其进行了修改。它使用 for 循环检查图中不同长度的循环数。到目前为止我得到的代码附在下面。

对于下图，

我得到的输出是

但是，答案不应该是3吗？

遵循 3 个独特的周期

0 -> 1 -> 2 -> 3 -> 0

0 -> 1 -> 4 -> 3 -> 0

1 -> 2 -> 3 -> 4 -> 1

我尝试使用以下代码为有向图实现“getCycles”函数：

其中 Vertex 类仅具有一个 String 字段，并且DiscoverStatus/getNeighbors定义为：

我的问题是：这种用于循环检测的“着色”算法（如果不熟悉，请参见此处）以某种方式提供检测“父”节点的方法吗？例如，使用以下有向图：

我在 C 上打了星号，因为它指向 A，在它们之间创建了一个循环。然而，A 是这里的父级。我怎样才能在getCycles算法或其他方面检测到这一点？起初我想我只是先进行深度优先搜索，看看一个是否包含另一个，然后我才意识到它们都相互包含。也许我应该这样做，但使用计数器变量来跟踪“深度”？我只是不知道如何开始。

问题：

编写一个程序，给出有向图中的循环数。

方法一：

我知道我们可以使用深度优先搜索来检测图中的循环，并以简单的布尔值形式返回答案。我在下面为此编写了代码。但是，我正在尝试在此代码中实现一个计数器，该计数器在每次检测到循环时都会递增。但无论我在哪里实施计数器，我似乎都没有得到正确的答案！（我已经在评论中写了增量语句）

我也担心 DFS 不是为这个问题选择的正确方法，因为周期之间可能存在一些共同的边缘。

循环检测算法取自：https ://www.geeksforgeeks.org/detect-cycle-in-a-graph/

下面给出的代码产生一个输出：

对于图表：

（这里说 0 个周期，因为注释计数增加了）

代码：

我还想知道是否可以使用图形着色方法找到解决方案，这就是我能够从中挖掘代码的方法： https ://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

方法 2：

算法：

• 创建一个接受边缘和颜色数组的递归函数（这也可以保存为全局变量）

• 将当前节点标记为灰色。

• 遍历所有相邻节点，如果任何节点标记为灰色，则
  返回 true，因为循环必然存在。

• 如果任何相邻顶点为白色，则调用该节点的递归函数。

• 如果函数返回true。返回真。

• 如果没有相邻节点是灰色的或没有返回true，则将当前节点标记为黑色并返回false。

代码：

当有多个解决方案时，我想返回课程按升序排列的解决方案。如何通过拓扑排序算法做到这一点？

我正在解决这个问题，给我带来麻烦的部分问题表述如下：

一个。从索引 i=0 开始；

湾。跳转到索引 i=A[i];

C。如果当前索引 i 超出 [0..N-1] 的有效范围，则打印“Out”并停止；

d。否则，如果当前索引 i 是索引 N-1，则打印“完成”并停止；

e1。否则，重复步骤b；

e2。如果这样做会导致无限循环，请打印“Cyclic”并停止；

（所有输出都没有引号）

arr是一个非负整数数组：

我在一些隐藏的测试用例上得到了 WA（错误答案），但我一辈子都想不出一个失败的测试用例。

• 1 2 3 4 5 0->Done
• 1 2 3 4 6 0->Out
• 1 0 0->Cyclic

编辑：

我的 C++ 解决方案有完全相同的失败测试用例，一定是我的逻辑...