Graph DFS method call stack unwinding confusion

Question

The broken method: hasPathDFSBroken Working version: hasPathDFS

The working version has a contrived param added to make it work which I'd rather avoid.

I'm trying to understand why in the broken version when the call stack starts unwinding at LIM as currNode and it gets back to MEX as the currentNode, why does it not resume the unfinished for loop over MEX's neighbors?

Any help would be greatly appreciated. Thanks!

const airports = "PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM".split(" ");

const routes = [
  ["PHX", "LAX"],
  ["PHX", "JFK"],
  ["JFK", "OKC"],
  ["JFK", "HEL"],
  ["JFK", "LOS"],
  ["MEX", "LAX"],
  ["MEX", "BKK"],
  ["MEX", "LIM"],
  ["MEX", "EZE"],
  ["LIM", "BKK"],
];

class Node {
  constructor(data) {
    this.data = data;
    this.neighbors = new Map();
  }

  addNeighbor(node) {
    this.neighbors.set(node.data, node);
    return this.neighbors.size;
  }

  getNeighbors() {
    return this.neighbors;
  }
}

class Graph {
  constructor(edgeDirection = Graph.UNDIRECTED) {
    this.nodes = new Map();
    this.edgeDirection = edgeDirection;
  }

  /* ???
  When the call stack starts unwinding at LIM as currNode and it gets back to MEX 
  as currNode, why doesn't the unfinished for loop resume over MEX's neighbors? 
  */
  hasPathDFSBroken(
    start,
    destination,
    currNode = this.nodes.get(start),
    visited = new Map()
  ) {
    if (!currNode) {
      return false;
    }

    visited.set(currNode.data, 1);

    console.log(
      "currNode:",
      currNode.data,
      "| neighbors:",
      [...currNode.getNeighbors().keys()],
      "| visited:",
      [...visited.keys()]
    );

    for (const [neighborData, neighborNode] of currNode
      .getNeighbors()
      .entries()) {
      console.log("currNeighbor:", neighborData);

      if (neighborData === destination) {
        return true;
      }

      if (!visited.has(neighborData)) {
        return this.hasPathDFSBroken(start, destination, neighborNode, visited);
      }
    }
    return false;
  }

  // Works but uses contrived found param for pass by ref.
  hasPathDFS(
    start,
    destination,
    currNode = this.nodes.get(start),
    visited = new Map(),
    found = { res: false }
  ) {
    if (!currNode) {
      return false;
    }

    visited.set(currNode.data, 1);

    console.log(
      "currNode:",
      currNode.data,
      "| neighbors:",
      [...currNode.getNeighbors().keys()],
      "| visited:",
      [...visited.keys()]
    );

    for (const [neighborData, neighborNode] of currNode
      .getNeighbors()
      .entries()) {
      console.log("currNeighbor:", neighborData);

      if (neighborData === destination) {
        return (found.res = true);
      }

      if (!visited.has(neighborData)) {
        this.hasPathDFS(start, destination, neighborNode, visited, found);
      }
    }
    return found.res;
  }

  addVertex(data) {
    if (this.nodes.has(data)) {
      return this.nodes.get(data);
    }
    const vertex = new Node(data);
    this.nodes.set(data, vertex);
    return vertex;
  }

  addEdge(source, destination) {
    const sourceNode = this.addVertex(source);
    const destinationNode = this.addVertex(destination);

    sourceNode.addNeighbor(destinationNode);

    if (this.edgeDirection === Graph.UNDIRECTED) {
      destinationNode.addNeighbor(sourceNode);
    }
    return [sourceNode, destinationNode];
  }

  addEdges(edges) {
    edges.forEach(([source, destination]) => this.addEdge(source, destination));
    return this;
  }

  print() {
    let str = [...this.nodes.values()]
      .map(
        (node) =>
          `${node.data} => ${[...node.getNeighbors().keys()].join(", ")}`
      )
      .join("\n");

    str = `${"_".repeat(100)}\n${str}\n${"_".repeat(100)}`;
    console.log(str);
    return str;
  }
}

Graph.UNDIRECTED = Symbol("directed graph"); // two-way edges
Graph.DIRECTED = Symbol("undirected graph"); // one-way edges

const flightPaths = new Graph().addEdges(routes);
flightPaths.print();

console.log(flightPaths.hasPathDFSBroken("HEL", "EZE"));
// console.log(flightPaths.hasPathDFS("HEL", "EZE")); // working ver.

Answer 1

why doesn't the unfinished for loop resume over MEX's neighbors?

Because the return statement you have inside the loop immediately breaks from the loop and the function.

Instead, you need to look at the return value and continue with the loop if the recursive call hasn't found the destination:

hasPathDFS(start, destination, currNode = this.nodes.get(start), visited = new Map()) {
  if (!currNode) {
    return false;
  }

  visited.set(currNode.data, 1);

  for (const [neighborData, neighborNode] of currNode.getNeighbors()) {
    if (neighborData === destination) {
      return true;
    }

    if (!visited.has(neighborData)) {
      const found = this.hasPathDFSBroken(start, destination, neighborNode, visited);
      if (found) return true;
//    ^^^^^^^^^^^^^^^^^^^^^^
      // else continue
    }
  }
  return false;
}

The pattern should become more obvious if you try to build a DFS that returns the path, not just a boolean whether the destination is reachable.

Btw, I'd recommend to use a Set for visited, and instead of checking neighborData === destination inside the loop rather do the base case comparison curreNode.data === destination outside of the loop (in fact, it's a bug, your version doesn't work for searching a path from a node to itself).