图DFS方法调用栈展开混乱

Question

破解方法：hasPathDFSBroken 工作版本：hasPathDFS

工作版本添加了一个人为的参数以使其工作，我宁愿避免。

我试图理解为什么在损坏的版本中，当调用堆栈作为 currNode 在 LIM 开始展开并返回到 MEX 作为 currentNode 时，为什么它不在 MEX 的邻居上恢复未完成的 for 循环？

如有任何帮助，我们将不胜感激。谢谢！

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?

因为循环中的 return 语句会立即从循环和函数中中断。

相反，如果递归调用没有找到目的地，您需要查看 return 值并继续循环：

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

如果您尝试构建一个 return 路径的 DFS，而不仅仅是目的地是否可达的布尔值，模式应该会变得更加明显。

顺便说一句，我建议对 visited 使用 Set，与其在循环内检查 neighborData === destination，不如在循环外进行基本情况比较 curreNode.data === destination循环（实际上，这是一个错误，您的版本不适用于搜索从节点到自身的路径）。

图DFS方法调用栈展开混乱

Graph DFS method call stack unwinding confusion

javascript

recursion

graph

depth-first-search

node.js