无向图DFS循环检测代码异常：存在循环却未被检出

问题根源分析 #

你的代码存在三个核心问题，导致无法正确检测无向图的循环：

1. 无向图边未双向添加
   无向图的边是双向的，但你的addEdge方法只向v的邻接表添加u，没有反向添加u到v的邻接表，导致实际构建的是有向图，破坏了无向图的结构。

2. forEach回调的return无法终止外层函数
   在isCyclicUtil中，你使用forEach遍历邻接节点，回调里的return true只能终止当前回调函数，无法让外层的isCyclicUtil立即返回true，因此即使检测到循环，最终函数还是会执行到末尾返回false。

3. 无向图循环检测逻辑错误
   你误用了有向图循环检测的dfsVisited（递归栈标记）方案。无向图的循环检测不需要递归栈标记，而是需要跟踪父节点，避免将从父节点来的反向边误判为循环。

修正后的代码 #

class Graph {
  constructor(V) {
    this.V = V;
    this.adj = {}; // 邻接表
  }

  // 添加顶点
  addVertex = (v) => {
    if (!this.adj[v]) {
      this.adj[v] = [];
    }
  };

  // 添加无向边（双向添加）
  addEdge = (v, u) => {
    this.adj[v].push(u);
    this.adj[u].push(v); // 新增反向边
  };

  // 递归辅助函数：跟踪父节点，检测循环
  isCyclicUtil = (source, visited, parentNode) => {
    visited[source] = true;
    
    // 改用for循环，方便控制返回逻辑
    for (const neighbor of this.adj[source] || []) {
      if (!visited[neighbor]) {
        // 递归遍历邻居，当前节点作为父节点传入
        if (this.isCyclicUtil(neighbor, visited, source)) {
          return true;
        }
      } 
      // 如果邻居已访问且不是父节点，说明存在循环
      else if (neighbor !== parentNode) {
        return true;
      }
    }
    return false;
  };

  hasCycle = () => {
    const visited = Array(this.V).fill(false);
    for (let i = 0; i < this.V; i++) {
      if (!visited[i] && this.isCyclicUtil(i, visited, -1)) { // 初始父节点设为-1（不存在的节点）
        return true;
      }
    }
    return false;
  };

  checkCycle = () => {
    if (this.hasCycle()) {
      console.log("存在循环。");
    } else {
      console.log("不存在循环");
    }
  };
}

const graph = new Graph(4);
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.checkCycle(); // 输出：存在循环。

关键修正说明 #

• 双向边添加：addEdge方法同时向两个顶点的邻接表添加对方，符合无向图的定义。
• 替换forEach为for循环：for循环可以在检测到循环时立即通过return终止外层函数，确保结果正确返回。
• 父节点跟踪逻辑：递归时传入当前节点的父节点，当遇到已访问且非父节点的邻居时，判定为存在循环，这是无向图循环检测的标准逻辑。
• 移除dfsVisited数组：无向图不需要递归栈标记，父节点跟踪足以区分正常反向边和循环。

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