3

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

出于某种原因，使用“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 有效？

4

1 回答 1

4

在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'));

于 2020-03-16T02:30:47.153 回答