请注意，图表示为邻接列表。
我听说过两种在图中查找循环的方法：
保留一个布尔值数组来跟踪您之前是否访问过某个节点。如果你用完了新的节点（没有到达你已经去过的节点），那么只需回溯并尝试不同的分支。
Cormen 的 CLRS 或 Skiena 中的一个：对于无向图中的深度优先搜索，有两种类型的边：树边和反向边。当且仅当存在后边时，图才有环。
有人可以解释一下什么是图的后边以及上述两种方法之间的区别吗？
谢谢。
更新： 这是在两种情况下检测循环的代码。 Graph 是一个简单的类，为了简单起见，将所有图节点表示为唯一的数字，每个节点都有其相邻的邻居节点（g.getAdjacentNodes(int)）：
public class Graph {
private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
public int[] getAdjacentNodes(int v) {
return nodes[v];
}
// number of vertices in a graph
public int vSize() {
return nodes.length;
}
}
检测无向图中循环的Java代码：
public class DFSCycle {
private boolean marked[];
private int s;
private Graph g;
private boolean hasCycle;
// s - starting node
public DFSCycle(Graph g, int s) {
this.g = g;
this.s = s;
marked = new boolean[g.vSize()];
findCycle(g,s,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v, int u) {
marked[v] = true;
for (int w : g.getAdjacentNodes(v)) {
if(!marked[w]) {
marked[w] = true;
findCycle(g,w,v);
} else if (v != u) {
hasCycle = true;
return;
}
}
}
}
检测有向图中的循环的Java代码：
public class DFSDirectedCycle {
private boolean marked[];
private boolean onStack[];
private int s;
private Graph g;
private boolean hasCycle;
public DFSDirectedCycle(Graph g, int s) {
this.s = s
this.g = g;
marked = new boolean[g.vSize()];
onStack = new boolean[g.vSize()];
findCycle(g,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adjacentNodes(v)) {
if(!marked[w]) {
findCycle(g,w);
} else if (onStack[w]) {
hasCycle = true;
return;
}
}
onStack[v] = false;
}
}
回答我的问题：
当且仅当存在后边时，图才有环。后边是从节点到其自身（自环）或 DFS 生成的树中其祖先之一的边，形成循环。
上面两种方法实际上意思是一样的。然而，这种方法只能应用于无向图。
该算法不适用于有向图的原因是，在有向图中，到同一顶点的 2 条不同路径不会形成循环。例如：A-->B、B-->C、A-->C - 不会形成循环，而在无向循环中：A--B、B--C、C--A 会形成循环。
在无向图中找到循环
当且仅当深度优先搜索 (DFS) 找到指向已访问顶点（后边）的边时，无向图才有循环。
在有向图中找到循环
除了访问过的顶点之外，我们还需要跟踪当前位于 DFS 遍历函数递归堆栈中的顶点。如果我们到达的顶点已经在递归堆栈中，那么树中就有一个循环。
更新： 工作代码位于上面的问题部分。
为了完整起见，可以使用 DFS 在有向图中找到循环（来自 wikipedia）：
L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily
add n to head of L
我认为上面的代码仅适用于连接的有向图，因为我们仅从源节点启动 dfs，因为如果有向图未连接，则其他组件中可能存在一个可能被忽视的循环！
这是我基于 DFS 用 C 语言编写的代码，用于查明给定的无向图是否是连通/循环的。最后有一些示例输出。希望对您有所帮助:)
#include<stdio.h>
#include<stdlib.h>
/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;
/****DFS Function Declaration****/
void DFS();
/****DFSearch Function Declaration****/
void DFSearch(int cur);
/****Main Function****/
int main()
{
int i,j;
printf("\nEnter no of Vertices: ");
scanf("%d",&n);
printf("\nEnter the Adjacency Matrix(1/0):\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
printf("\nThe Depth First Search Traversal:\n");
DFS();
for(i=1;i<=n;i++)
printf("%c,%d\t",'a'+seq[i]-1,i);
if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!");
if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!");
if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!");
if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!");
printf("\n\n");
return 0;
}
/****DFS Function Definition****/
void DFS()
{
int i;
for(i=1;i<=n;i++)
if(!visited[i])
{
if(i>1) connected=0;
DFSearch(i);
}
}
/****DFSearch Function Definition****/
void DFSearch(int cur)
{
int i,j;
visited[cur]=++count;
seq[count]=cur;
for(i=1;i<count-1;i++)
if(A[cur][seq[i]])
acyclic=0;
for(i=1;i<=n;i++)
if(A[cur][i] && !visited[i])
DFSearch(i);
}
示例输出：
majid@majid-K53SC:~/Desktop$ gcc BFS.c
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 10
Enter the Adjacency Matrix(1/0):
0 0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10
It is a Not-Connected, Cyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 4
Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1
The Depth First Search Traversal:
a,1 c,2 b,3 d,4
It is a Connected, Acyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 5
Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5
It is a Not-Connected, Acyclic Graph!
*/
在此提供关于问题子集的观察：如果
num_edgesnum_nodes更新：还提供了使用 DFS 检测无向图中循环的 Python 代码。非常感谢您对此进行优化的帮助。
def detect_cycle(graph, root):
# Create an empty stack
stack = []
# Track visited nodes
visited = [False] * graph.num_nodes
# Track the order of traversal
traversal = []
# Track parents of traversed nodes
parent = [None] * graph.num_nodes
# Begin Traversal
stack.append(root)
parent[root] = root
while len(stack) > 0:
# Pop the stack
node = stack.pop()
if not visited[node]:
visited[node] = True
traversal.append(node)
# Check the neighbors for visited nodes, or continue traversal
for neighbor in graph.edges[node]:
if not visited[neighbor]:
stack.append(neighbor)
parent[neighbor] = node
# If the neighbor is visited, check for back edge
# If a back edge exists, neighbor will have been visited before
# the parent of the current node
elif traversal.index(neighbor) < traversal.index(parent[node]):
return (f'Cycle at node {node}!')
return ('Acyclic graph!')