Skip to content

Instantly share code, notes, and snippets.

@LarryBattle
Forked from kevinfjbecker/bfs.html
Last active March 10, 2016 16:52
Show Gist options
  • Save LarryBattle/9d48a65c9d0f5136ccb0 to your computer and use it in GitHub Desktop.
Save LarryBattle/9d48a65c9d0f5136ccb0 to your computer and use it in GitHub Desktop.
Breadth-first Graph Traversal in ES6
"use strict";
const G = {
vertices: [{
edges: [1, 4]
}, {
edges: [0, 2, 3, 4]
}, {
edges: [1, 3]
}, {
edges: [1, 2, 4]
}, {
edges: [0, 1, 3]
}]
};
let bfs = (vertices, s) => {
let vs = vertices.map((v, i) => {
return Object.assign( {}, v, {color: 'white', distance: Infinity, parent: null, id: `edge ${i}`});
});
Object.assign(vs[s], {color: 'grey', distance: 0});
let Q = [s];
while (Q.length) {
let v = vs[Q.shift()];
const d = v.distance+1;
v.edges.filter(e => vs[e].color === 'white').forEach(e => {
Object.assign(vs[e], { color: 'grey', distance: d, parent: v.id});
Q.push(e);
});
v.color = 'black';
}
return vs;
};
console.log( JSON.stringify( bfs(G.vertices, 0), null, 2) );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment