{{ message }}

Instantly share code, notes, and snippets.

# DmitrySoshnikov/dfs-bfs-non-recursive.js

Created Oct 19, 2015
Non-recursive DFS and BFS algorithms
 /** * 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 * 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));

### BarthesSimpson commented Jul 28, 2017

 I think you will get wrong order if you do queue.unshift(n) in line 131. I think it needs to be queue.push(n)

 +1

 +2