基于DFS实现无向图环检测的Java代码测试失效，排查代码逻辑缺陷

核心缺陷定位 #

当前实现的根本问题是破坏了DFS遍历的完整性，在分支处理过程中出现了提前中断，导致大量邻接分支根本没有被遍历到，进而出现环检测漏判的问题。

具体错误点拆解 #

• 递归分支的提前返回逻辑错误
  在处理未访问的邻接节点时，代码直接将递归调用的结果作为当前函数的返回值，没有完成当前节点全部邻接节点的遍历就退出函数。比如当一个节点同时连接两个独立分支时，只要第一个分支没有检测到环，代码就会直接向上返回无环结果，完全跳过对第二个分支的环检测，哪怕第二个分支本身存在环也无法被识别。
• 遍历流程的逻辑断层
  正常DFS遍历当前节点时，需要逐次处理所有邻接节点：如果某个未访问邻接节点的递归分支检测到环，才可以立刻向上返回存在环的结果；如果递归分支没有检测到环，必须回到当前节点，继续处理下一个邻接节点，直到所有邻接节点处理完成，才能向上返回无环的判定。

修正后的核心实现 #

调整isCyclicUtil的返回逻辑，仅当递归分支明确检测到环时才中断遍历，否则持续处理剩余邻接节点：

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]) {
            // 仅当递归分支检测到环时，才中断遍历向上返回
            if (isCyclicUtil(nextNode, visited, current, adj)) {
                return true;
            }
        } 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;
}

典型漏判场景说明 #

以邻接表adj = [[1,2], [0], [0,3], [2]]（共4个节点，结构为0连接1、2，2连接3，形成2-3-2的环）为例，原代码会走到节点0时先处理邻接节点1：

1. 递归进入节点1的遍历，仅检测到邻接节点0为父节点，无环返回false
2. 原代码直接将这个false结果作为节点0的返回值向上传递，完全跳过对邻接节点2的处理，最终错误判定整个图无环
   修正后的代码会在节点1的分支遍历完成后，继续回到节点0处理邻接节点2，最终可以正确检测到2-3之间的环结构。

内容的提问来源于stack exchange，提问作者Vivek Kumar