DmitrySoshnikov · October 19, 2015 05:40 · Oct 19, 2015
diff --git a/dfs-bfs-non-recursive.js b/dfs-bfs-non-recursive.js
@@ -0,0 +1,143 @@
+/**
+ * Depth-first and Breadth-first graph traversals.
+ *
+ * In this diff we implement non-recursive algorithms for DFS,
+ * and BFS maintaining an explicit stack and a queue.
+ *
+ * by Dmitry Soshnikov <[email protected]>
+ * MIT Style license
+ */
+
+class Node {
+  constructor(name, childNodes) {
+    this.name = name;
+    this.childNodes = childNodes;
+    this.visited = false;
+  }
+}
+
+// Nodes.
+let A = new Node('A');
+let B = new Node('B');
+let C = new Node('C');
+let D = new Node('D');
+let E = new Node('E');
+let F = new Node('F');
+let G = new Node('G');
+let H = new Node('H');
+
+let allNodes = [A, B, C, D, E, F, G, H];
+
+function resetNodes() {
+  allNodes.forEach(node => {
+    node.visited = false;
+  });
+}
+
+resetNodes();
+
+// Graph.
+A.childNodes = [B, D, G];
+B.childNodes = [E, F];
+C.childNodes = [F, H];
+D.childNodes = [A, F];
+E.childNodes = [B, G];
+F.childNodes = [B, C, D];
+G.childNodes = [A, E];
+H.childNodes = [C];
+
+// ---------------------------------------------------------------
+// 1. DFS
+// ---------------------------------------------------------------
+
+// DFS maintains an explicit stack of working nodes.
+
+let stack = [];
+
+// Before the beginning, the stack should contain
+// the start node. We start from A.
+stack.push(A);
+
+let output = [];
+
+function DFS() {
+  stackLoop: while (stack.length) {
+    // The top of the stack is our working node.
+    let node = stack[stack.length - 1];
+
+    // Visit the node if it's not visited yet.
+    if (!node.visited) {
+      node.visited = true;
+      output.push(node);
+    }
+
+    // Get next node to visit.
+    for (let n of node.childNodes) {
+      if (!n.visited) {
+        // Found the node, just go to the DFS
+        // loop for it, pushing it onto the stack.
+        stack.push(n);
+        continue stackLoop;
+      }
+    }
+
+    // If we reach here, all child nodes were visited,
+    // so just pop the node from the stack.
+    stack.pop();
+  }
+}
+
+DFS();
+
+// DFS: [ 'A', 'B', 'E', 'G', 'F', 'C', 'H', 'D' ]
+console.log('DFS:', output.map(n => n.name));
+
+// Exercise: Implement a recursive version (basically, using
+// the call-stack for the purposes of the algorithm)
+
+// ---------------------------------------------------------------
+// 2. BFS
+// ---------------------------------------------------------------
+
+
+// Clear visited flag.
+resetNodes();
+output = [];
+
+// BFS maintains a queue of working nodes.
+
+let queue = [];
+
+// Enqueue the start node, A.
+queue.unshift(A);
+
+function BFS() {
+  queueLoop: while (queue.length) {
+    // Get the next queued node to work on.
+    let node = queue.shift();
+
+    // Visit the node if it's not visited yet.
+    if (!node.visited) {
+      node.visited = true;
+      output.push(node);
+    }
+
+    // Visit all direct child nodes, and
+    // enqueue them.
+    for (let n of node.childNodes) {
+      if (!n.visited) {
+        n.visited = true;
+        output.push(n);
+        queue.unshift(n);
+      }
+    }
+
+    // Go to the next node from the queue
+    // on the following iteration.
+  }
+}
+
+BFS();
+
+// BFS: [ 'A', 'B', 'D', 'G', 'E', 'F', 'C', 'H' ]
+console.log('BFS:', output.map(n => n.name));