javascript - JS Graph递归与迭代DFS顺序差异

Question

我查找了迭代图 DFS，它显示使用堆栈作为边缘，但这会产生与递归 DFS 不同的顺序。我也尝试对迭代 DFS 使用队列，但获得与递归 DFS 相同顺序的唯一方法是使用一堆 Map 迭代器返回并恢复边缘上的迭代，但我觉得可能有更好的方法方法来做到这一点。

我已经包含了每个 DFS 方法、递归、迭代堆栈、迭代队列和迭代 Map 迭代器以及每个被记录的顺序：

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

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

/**
 * Represents a Node (vertex / point) in a Graph and stores it's connections to
 * other Nodes (edges).
 */
class Node {
  /**
   * Constructs a new node with the given data.
   * @param {NodeData} data
   * @returns {Node} This new node.
   */
  constructor(data) {
    this.data = data;
    this.edges = new Map();
  }

  addEdge(node) {
    this.edges.set(node.data, node);
    return this.edges.size;
  }

  getEdges() {
    return this.edges;
  }
}

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

  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.addEdge(destinationNode);

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

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

  // recursive
  toArrDFS(start, currNode = this.nodes.get(start), visited = new Set()) {
    if (!currNode) {
      return [...visited];
    }

    visited.add(currNode.data);

    for (const edge of currNode.getEdges().values()) {
      if (!visited.has(edge.data)) {
        this.toArrDFS(start, edge, visited);
      }
    }
    return [...visited];
  }

  // Iterative stack - not same order recursive DFS
  toArrIterativeDFS(start) {
    const startNode = this.nodes.get(start);

    if (!startNode) {
      return [];
    }

    const stack = [startNode];
    const visited = new Set();

    while (stack.length) {
      const currNode = stack.pop();
      visited.add(currNode.data);

      for (const edge of currNode.getEdges().values()) {
        if (!visited.has(edge.data)) {
          stack.push(edge);
        }
      }
    }
    return [...visited];
  }

  // Iterative queue - not same order recursive DFS
  toArrIterativeDFS2(start) {
    const startNode = this.nodes.get(start);

    if (!startNode) {
      return [];
    }

    const queue = new Set([startNode]);
    const visited = new Set();

    while (queue.size) {
      const currNode = queue.values().next().value;

      if (!currNode) {
        continue;
      }

      queue.delete(currNode); // O(1) dequeue.
      visited.add(currNode.data);

      for (const edge of currNode.getEdges().values()) {
        if (!visited.has(edge.data)) {
          queue.add(edge);
        }
      }
    }
    return [...visited];
  }

  // Stack of Map iterators - Same order recursive DFS
  toArrIterativeDFS3(start) {
    const startNode = this.nodes.get(start);

    if (!startNode) {
      return [];
    }

    const iteratorsStack = [startNode.getEdges().values()];
    const visited = new Set([startNode.data]);

    while (iteratorsStack.length) {
      const currIter = iteratorsStack.pop();
      const nxt = currIter.next();

      if (!nxt.done) {
        const node = nxt.value;
        iteratorsStack.push(currIter);
        !visited.has(node.data) &&
          iteratorsStack.push(node.getEdges().values());

        visited.add(node.data);
      }
    }
    return [...visited];
  }

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

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

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

const flightPaths = new Graph().addEdges(routes);
flightPaths.print();
console.log("recursive DFS", flightPaths.toArrDFS("HEL"));
console.log("iterative DFS Stack", flightPaths.toArrIterativeDFS("HEL")); // not same order as recursive
console.log("iterative DFS Queue", flightPaths.toArrIterativeDFS2("HEL")); // not same order as recursive
console.log(
  "iterative DFS stack of Map Iterators",
  flightPaths.toArrIterativeDFS3("HEL")
); // same  order as recursive

标签： javascriptnode.jsdepth-first-search

Answer 1

您的 map 迭代器堆栈具有与递归版本相同的结果顺序，因为它准确地表示了for递归函数中循环的状态。

为了对比您的简单堆栈版本，请查看在所有边缘都被推入堆栈之后处理边缘的顺序：下一次迭代采用最后一个被推入的顶部；然后是倒数第二个等等，基本上以相反的顺序处理边缘。

如果要重现与递归版本相同的结果，则必须反向堆叠每个节点的邻居。此外，如果它们同时被访问过（即如果它们被多次放入堆栈），您将希望再次跳过处理它们。

toArrIterativeDFS(start) {
  const stack = [];
  const visited = new Set();
  const startNode = this.nodes.get(start);
  if (startNode) {
    stack.push(startNode);
  }

  while (stack.length) {
    const currNode = stack.pop();
    if (!visited.has(currNode.data)) {
      visited.add(currNode.data);

      stack.push(...Array.from(currNode.getEdges().values()).reverse());
    }
  }
  return Array.from(visited);
}