使用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;
}

某些测试用例失败了，我无法弄清楚代码哪里出了问题。请帮助我理解代码中的错误。

- Vivek Kumar

---

请分享问题的链接。如果可能，请分享任何输入实例，以便我们找出错误所在。我已经对它进行了几次测试，它们都能够正确地工作。 - AKSingh

https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1 - Vivek Kumar

Answer 1

在不访问所有相邻顶点的情况下，由于 return 语句的存在，您在访问第一个未被访问的相邻顶点后停止探索它们：

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

一次 isCyclicUtil 执行的搜索空间实质上是一条路径，某些顶点将不会被访问。当然，在 isCycle 函数中的某个后续迭代中它们将被访问，但了解为什么有些循环可能无法通过这种方式检测出来可能是一个不错的练习。

修复很容易 - 只有在实际找到循环时才返回。

- stiar

---

非常感谢。按照下面所述更改代码可行： code if (!visited[nextNode]) { if(isCyclicUtil(nextNode, visited, current, adj)) return true; } else { if (nextNode != parent) return true; } code - Vivek Kumar