JavaScript图迭代DFS问题：无法向visited集合添加元素求助

迭代DFS的问题分析及修复 #

你的迭代DFS存在两个核心问题：

1. visited集合更新时机错误
   你在处理当前节点时直接把所有邻居加入visited，会导致未访问甚至未入栈的节点被提前标记为已访问，破坏DFS遍历逻辑。正确逻辑是节点入栈时就标记为已访问，避免重复入栈。
2. 默认参数陷阱
   JS中visited = new Set()这类默认参数只会初始化一次，多次调用函数会复用同一个Set，导致后续测试结果被之前的调用污染，需要在函数内部创建新的Set。

另外，原代码的邻居入栈顺序会导致遍历结果和示例反向（栈是后进先出），可以通过反转邻居数组匹配示例输出顺序。

修正后的迭代DFS代码

const adjList = {
  1: [2, 5],
  2: [1, 3, 5],
  3: [2, 4],
  4: [3, 5, 6],
  5: [1, 2, 4],
  6: [4]
}

function printDepthFirst(start) {
  const visited = new Set();
  const stack = [];
  const visitedArr = [];

  stack.push(start);
  visited.add(start);

  while (stack.length > 0) {
    const node = stack.pop();
    visitedArr.push(node);
    console.log(" Visited Node: " + node);

    // 反转邻居数组，保证遍历顺序和示例一致（可选，按需调整）
    const neighbors = adjList[node].reverse();
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
        visited.add(neighbor); // 入栈时标记为已访问
      }
    }
  }

  console.log("Visited Nodes: " + JSON.stringify([...visited]))
  console.log("VisitedArr: " + visitedArr)
  return visitedArr;
}

console.log("First Test:")
printDepthFirst(3); // 输出：3, 4, 6, 5, 1, 2
console.log("Second Test:")
printDepthFirst(6); // 输出：6, 4, 5, 2, 1, 3
console.log("Third Test:")
printDepthFirst(4); // 输出：4, 6, 5, 2, 1, 3

递归式DFS实现 #

递归DFS逻辑更直观：访问当前节点并标记，然后递归遍历所有未访问的邻居。同样要注意避免默认参数陷阱，每次调用初始化新的visited集合。

function printDepthFirstRecursive(start, visited = null) {
  // 每次调用初始化新Set，规避默认参数陷阱
  if (visited === null) {
    visited = new Set();
  }
  visited.add(start);
  console.log(" Visited Node: " + start);
  const visitedArr = [start];

  // 反转邻居数组匹配示例顺序
  const neighbors = adjList[start].reverse();
  for (const neighbor of neighbors) {
    if (!visited.has(neighbor)) {
      // 递归调用并拼接结果
      visitedArr.push(...printDepthFirstRecursive(neighbor, visited));
    }
  }

  // 仅在首次调用时打印完整结果，避免递归过程重复输出
  if (visited.size === Object.keys(adjList).length) {
    console.log("Visited Nodes: " + JSON.stringify([...visited]))
    console.log("VisitedArr: " + visitedArr)
  }
  return visitedArr;
}

// 测试递归版本
console.log("Recursive Test 1:")
printDepthFirstRecursive(3);
console.log("Recursive Test 2:")
printDepthFirstRecursive(6);

内容的提问来源于stack exchange，提问作者Timothy W. Times