Skip to content

Instantly share code, notes, and snippets.

@ORESoftware ORESoftware/bfs.js
Last active Apr 12, 2019

Embed
What would you like to do?
Simple breadth first traversal example
'use strict';
const queue = [];
const root = {};
const main = {
name: 'main',
linkedSet:{
a: {
name: 'a',
linkedSet: {}
},
b: {
name: 'b',
linkedSet: {
c: {
name: 'c',
linkedSet: {}
},
d: {
name: 'd',
linkedSet: {
e: {
name: 'e',
linkedSet: {
i: {
name: 'i',
linkedSet: {}
}
}
}
}
},
f: {
name: 'f',
linkedSet: {
g: {
name: 'g',
linkedSet: {
h: {
name: 'h',
linkedSet: {}
}
}
}
}
}
}
}
}
};
let counter = 0;
const addBreadthFirst = (currTreeNode, dep) => {
for (let v of Object.values(dep.linkedSet)) {
if (v.visited) {
continue;
}
v.visited = true;
queue.push([currTreeNode[v.name] = {count: counter++}, v]);
}
const next = queue.shift();
if(next){
addBreadthFirst(...next);
}
};
addBreadthFirst(root, main);
console.log(JSON.stringify(root));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.