无向图中查找环的算法有哪些 比较直观的办法是，从初始结点 S 开始，用深度优先的方法遍历图的结点，如果在这个过程中，你遇到了一个先前就已经发现过的结点（假定它叫 V），说明存在一个环。如果你想。
麻烦问下各路大牛 怎么求无向图中的最小环长度？ 万分感谢 我用的是Dijsktra算法进行的计算。假设一个环中有两个顶点A，B，那么走完这个环的最小路程是从A到B的最短路+去掉A到B的最短路上的所有路径后的A到B（B到A）的最短路（就相当于是从A走到B再走到A的最短路）因此，在外层枚举A，算出A到各个点的最短路，同时记下路径。然后枚举每一个B，删掉A到B上最短路径所经过的边，再算一次A到B的最短路径，然后两者相加，求得一个环的最短路。最后找一个最小的环的长度，输出即可。时间复杂度到了O(n^4)，所以我有一组花了0.9s.但是这道题的难点在于那个BT的INPUT-从来都没有见过的图的输入方式：告诉的是边与边的关系。我是这样解决的：找出所有的边的两个端点（不管是否重复），并把这些端点连了哪些边记录下来。然后去掉重复的顶点，剩下的就是图的顶点。接着通过枚举寻找任意两个顶点是否都连了相同的边，如果连了，说明这两个顶点就是被这条边所连，因此就可以在邻接矩阵中记录下来。时间复杂度O(n^3)这一题是我一次AC的。难得在USACO Cheapter4 里面一次AC哈。Cherry还有更好的O(n^3)的算法，我也不知道怎么做的。感兴趣的去看一下子。
无向图中找所有环（最好有程序PASCAL) 如果要输出所有解得用DFS搜索（递归实现）算法大致如下：1、搜索以x[1]开头的，标记x[1]访问，2、递归处理x[2]3、停止条件，碰到访问过的就输出一组解然后跳出procedure dfs(dep：longint)；var i：longint；beginif dep=n then exit；for i：=1 to n doif v[i]thenbeginfor i：=1 to dep do write(x[i])；writeln；end；elsebeginx[dep+1]：=i；dfs(dep+1)；x[dep+1]：=0；end；end；begin读入图；dfs(0)；end.时间复杂度O（n。有问题qq 343182185
