JS图递归与迭代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

Answer 1

映射迭代器堆栈的结果顺序与递归版本相同，因为它准确地表示了递归函数中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);
}