Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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 <dmitry.soshnikov@gmail.com>
* 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

This comment has been minimized.

Copy link

@BarthesSimpson 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)

@vsel

This comment has been minimized.

Copy link

@vsel vsel commented Mar 17, 2018

+1

@Belyenochi

This comment has been minimized.

Copy link

@Belyenochi Belyenochi commented Sep 8, 2018

+2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment