使用DFS检测无向图中的循环

Question

我正在尝试检测无向图中的循环。我正在使用DFS来检测相同的情况。对于任何节点，我都会通过所有连接的节点进行访问。如果子节点已经被访问，并且它不是当前节点的父节点，那么我们在图中有一个循环。

我写了以下代码：

public boolean isCyclicUtil(int current, boolean[] visited, int parent, ArrayList<ArrayList<Integer>> adj) {
visited[current] = true;
Iterator<Integer> it = adj.get(current).iterator();
while (it.hasNext()) {
int nextNode = it.next();
if (!visited[nextNode]) {
return isCyclicUtil(nextNode, visited, current, adj);
} else {
if (nextNode != parent)
return true;
}
}
return false;
}
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i] && isCyclicUtil(i, visited, -1, adj)) {
return true;
}
}
return false;
}

它在某些测试用例中失败了。我不知道代码出了什么问题。请帮助我理解代码中的错误。

Answer 1

不是访问所有相邻的顶点，而是在访问第一个尚未访问的相邻顶点后停止对其进行探索，因为返回语句：

if (!visited[nextNode]) {
return isCyclicUtil(nextNode, visited, current, adj);
}

单个isCyclicUtil执行的搜索空间实质上变成了一条路径，并且某些顶点将不会被访问。当然，它们将在isCycle函数的稍后迭代中被访问，但理解为什么某些循环可能无法以这种方式检测可能是一个很好的练习。

修复很容易——只有当你真的找到了一个循环时，你才想返回。