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

由于 return 语句：

，您在访问尚未访问的第一个相邻顶点后停止探索它们，而不是访问所有相邻顶点

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

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

修复很容易 - 只有当您确实找到了一个循环时，您才想 return。

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

Detect cycle in an undirected graph using DFS

java

algorithm

graph

breadth-first-search

depth-first-search