<分区>
我正在尝试检测无向图中的循环。我正在使用 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;
}
某些测试用例失败。我无法弄清楚代码有什么问题。 请帮助我了解代码中的错误。