为什么在执行递归回调时 .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) returns ['A', 'B', 'D', 'E', 'C', 'F' ]，哪个是对的。

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

作为参考，图表如下所示：

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

Answer 1

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

return 值在这里无关紧要，returning 除了引入此错误外没有任何作用。最好从两个版本中删除 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'));

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

Why does .foreach behave differently than for...of when executing a recursive callback?

javascript

algorithm

recursion

foreach

for-of-loop