多重图中的圈检测
我想在一个无向多图中列出所有的圈。
Tarjan的强连通分量算法是针对有向图编写的。它适用于多图吗？如果没有，有无向多图的圈列算法吗？
共有1个答案
-
我试图在有向图中检测一个循环 在提出解决该问题的逻辑时，我发现一个简单的图遍历等式dfs就足够了，因为在执行dfs时，我们可以有一个条件来查看是否已经访问了任何节点。如果是这样，就必须有一个循环 在查找交叉检查逻辑的解决方案时，我遇到了这样一个解决方案，即在执行dfs的同时跟踪访问的节点，您还需要跟踪递归堆栈中的节点，如果一个节点已经在递归堆栈中，那么就有一个循环-我不理解 当我们可以简单地检查是
-
因此DFS应该检测有向图中的圈。如果它到达了一个以前已经访问过的节点，即它找到了一个后沿，那么我们有一个循环。
-
我正在编写一个使用电网格分析的程序。所以我有电路的节点[A,B,C,D]和连接节点[0,1,2,3,4,5,6,7,8]的分支。 如何在具有多条边的无向图中找到最短的循环？ 图形图像（4个节点，9条边/分支）： 周期： 我需要的循环数是：循环=分支-（节点-1)，在本例中我需要6个循环。 我将这些数据存储在这样的数组中： 我很乐意看到任何语言的算法。
-
我有这个结构 这包括： 我想检查一下图中的是循环。我是用DFS alghoritm来做的——若我访问了被访问的节点，那个么图中是循环。这是我的alghoritm： 但我还是得到了同样的错误——alghoritm告诉我，在图形中，始终是循环的，不管输入是什么。提前感谢你们的帮助。
-
我正在努力实现如下图所示 我已经设法创建css圈与图标在它，但文字后是不符合Cirlce。
-
算法： 图表： (1)-------(2) 邻接列表： [1] - [2] - 不相交集： {{1}, {2}} 迭代1： 边e=（1，2） 联盟（1,2） 不相交集={{1，2}} 迭代2： 边e=（2，1） 2和1都属于同一个集合，所以算法检测到一个循环，很明显图不包含循环。 对于有向图，该算法可以完美地工作。请帮我分析一下。