javascript - 为什么在执行递归回调时 .foreach 的行为与 for...of 不同？

Question

我正在使用邻接列表编写递归深度优先图遍历，邻接列表是一个对象，包含顶点作为键，每个键的邻居数组作为值。辅助函数被递归调用以访问初始顶点的所有邻居，然后是这些邻居的所有邻居，等等。

出于某种原因，使用“for...of”循环遍历每个相邻数组无法正常工作。辅助函数将在邻居的邻居的邻居上调用，但是当达到基本情况时，辅助函数似乎不会在初始邻居的其他邻居上调用，所以你最终会死 -永远达不到的目的。

  function depthFirstRecursiveTraversal(initialVertex) {
    const adjacencyList = {
      A: ['B', 'C'],
      B: ['A', 'D'],
      C: ['A', 'E'],
      D: ['B', 'E', 'F'],
      E: ['C', 'D', 'F'],
      F: ['D', 'E']
    };
    let visited = {};
    let vertexList = [];

    function dfsHelper(v) {
      if (!v) return null;
      vertexList.push(v);
      visited[v] = true;

      // Why does a for-of loop fail here? Recursion fails to reach all vertices
      //for (const neighbor of adjacencyList[v]) {
      //  if (!visited[neighbor]) return dfsHelper(neighbor);
      //}

      // But using forEach instead works!
       adjacencyList[v].forEach(neighbor => {
         if (!visited[neighbor]) return dfsHelper(neighbor);
       });

    }
    dfsHelper(initialVertex);

    return vertexList;
  }

调用 depthFirstRecursiveTraversal(A) 返回 [ 'A', 'B', 'D', 'E', 'C', 'F' ]，这是正确的。

但是，如果您注释掉 forEach 并在 for...of 循环中注释，它会返回 [ 'A', 'B', 'D', 'E', 'C' ] -- 'F'永远不会到达顶点。

作为引用，这是图表的样子:

         A
       /   \
      B     C
      |     |
      D --- E
       \   /
         F

谁能告诉我为什么 for...of 失败，但 foreach 有效？

Answer 1

在for 循环中，return 将终止整个dfsHelper 函数。相反，在 forEach 回调中，return 只是终止回调。

返回值在这里无关紧要，返回除了引入这个错误之外没有任何作用。最好从两个版本中删除 return - 如果你这样做，for..of 工作正常:

function depthFirstRecursiveTraversal(initialVertex) {
  const adjacencyList = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'E'],
    D: ['B', 'E', 'F'],
    E: ['C', 'D', 'F'],
    F: ['D', 'E']
  };
  let visited = {};
  let vertexList = [];

  function dfsHelper(v) {
    if (!v) return null;
    vertexList.push(v);
    visited[v] = true;

    for (const neighbor of adjacencyList[v]) {
      if (!visited[neighbor]) dfsHelper(neighbor);
    }

  }
  dfsHelper(initialVertex);

  return vertexList;
}
console.log(depthFirstRecursiveTraversal('A'));