有向图中循环的检测
我在这里读到一篇关于在有向图中求圈的讨论。现在,OP声称我们需要验证两件事：
- 从
U到V有一个后沿
v在递归堆栈 中
为什么我们需要第二次测试？你能举个例子来说明它的必要性吗？
共有1个答案
你可能混淆了有向图的后边和无向图的后边的定义。是的，他们不一样。
而在无向图中，后边是从当前顶点到已访问顶点的边。（正如您的链接中提到的操作）。
在有向图中，后边的定义是不同的。有向图中的后边是从当前顶点到灰色顶点的边（该顶点的DFS已开始但尚未完成），这意味着它仍在递归堆栈中。
因此，如果您将后边的定义作为有向图中的定义，那么是的，它足以检测循环。
但是如果您将后边的定义作为无向图中的定义，那么您还需要确保v在递归堆栈中，以便检测循环。
有关更多信息和示例，请参阅此和此。
-
目前我正在用这个样本进行拓扑排序，并对https://www.geeksforgeeks.org/topological-sorting/做了一些修改 我用它来排序要求解的变量的顺序。 样本 每个变量都有一个唯一整数，并存储在一个映射中 创建图形并添加边时，总共有4个顶点，因此我的代码将像这样构造图形 排序并按相反顺序得到结果后，它是正确的c 一切都很好，但我需要检测图中的循环引用。假设变量是 有
-
我们可以用这里所述的算法求有向图中的圈数。我需要理解算法。 （1）最后那句话到底有什么用处？对algo的工作原理进行简短的描述会很有帮助。由于算法基本上是统计从一个节点返回到同一节点的周期数，所以我们可以使用另一个数组，称之为v，并做以下技巧： （2）我不能实现我刚才写的算法。这是主要的问题，但我认为我需要理解上面的（1）来理解打印所有循环的代码。 我了解到互联网上有算法，我正在尝试使用这个算法。
-
我有一个带边的无向图。每条边都具有一定的性质，如A点和B点之间的边之一是 在C点和D点之间的另一个可以是 我们得到了这样一个图和已知的旅行路径 有快一点的吗？
-
因此，我为DFS编写了以下代码： 现在，我读到，在一个无向图中，如果当DFS时，它再次返回到同一个顶点，有一个循环。所以我做的是这样,， 但是，我的检查周期函数返回true，即使他们没有周期。那是为什么呢？我的功能有问题吗？没有执行问题，否则我早就调试了，但他们似乎在我的逻辑中有问题。
-
这是我的代码；
-
我有一个无向图，它被加载为邻接矩阵。我有一个使用BFS算法检测图中循环的方法。我试图实现的是打印所有的边缘，以一种方式，他们表明一个循环，已经找到。 我可以打印一个图形中的所有边，但我不能只打印那些创建循环的边。我怎么让它工作？ 边缘： 图表： 节点： 当前错误输出：显示一个周期的部分边沿，但不是全部边沿 预期输出：打印创建循环的所有边,如上面的示例所示, 我想显示:一条边的结束顶点是循环中另一条