Почему .foreach ведет себя иначе, чем ... при выполнении рекурсивного обратного вызова?

Question

Я пишу рекурсивный обход графика в глубину, используя список смежности, который представляет собой объект, содержащий вершины в качестве ключей и массив соседних ключей в качестве значений. Вспомогательная функция вызывается рекурсивно для посещения всех соседей начальной вершины, а затем всех соседей этих соседей и т. Д. c.

По какой-то причине использование «for ... of» l oop для итерации по каждому соседнему массиву не работает должным образом. Вспомогательная функция будет вызываться на соседе соседа соседа, но затем, когда достигается базовый случай, вспомогательная функция, по-видимому, не вызывается на других соседях первоначального соседа, поэтому вы в конечном итоге получаете Концы, которые никогда не достигаются.

  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;
  }

Вызов глубиныFirstRecursiveTraversal (A) возвращает ['A', 'B', 'D', 'E', 'C', 'F'], что является правильным.

Но если вы закомментируете forEach и комментируете в for ... of l oop, он возвращает ['A', 'B', 'D', 'E', 'C '] - вершина' F 'никогда не достигается.

Для справки, вот как выглядит график:

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

Может кто-нибудь сказать мне, почему ... неудачи, но foreach работает?

Answer 1

Внутри for l oop, 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'));