I looked up iterative Graph DFS and it showed using a stack for the edges but this is producing a different order vs recursive DFS. I tried using a queue for the iterative DFS as well but the only way I could get the same order as recursive DFS was using a stack of Map iterators come back to and resume the iteration over edges, but I feel like there is probably a better way to do it.
I've included each DFS method, recursive, iterative stack, iterative queue, and iterative Map iterators with the order of each being logged:
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
Your stack of map iterators has the same result order as the recursive version because it accurately represents the state of the for loop in the recursive function.
To contrast your simple stack version, look at the order in which edges are processed after all of them have been pushed onto to the stack: the next iteration takes the top one, which was pushed last; then the second-to-last and so on, essentially processing the edges in reverse order.
If you want to reproduce the same result as the recursive version, you have to stack the neighbors of each node in reverse. Also you'll want to skip processing them again if they have been visited in the meantime (i.e. if they had been put on the stack multiple times).
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);
}