Skip to content

Instantly share code, notes, and snippets.

@robbywashere robbywashere/bfs.js
Created Jan 15, 2019

Embed
What would you like to do?
class Graph {
constructor(){
this.nodes = {};
}
addNode(n){
if (!this.nodes[n]) this.nodes[n] = [];
}
addEdge(a,b){
this.nodes[a].push(b);
}
}
let g = new Graph();
g.addNode(0);
g.addNode(1);
g.addNode(2);
g.addNode(3);
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
function bfs(graph,node){
const visited = new Set();
let q = [node];
visited.add(node);
while (q.length) {
let newNode = q.pop();
console.log(newNode);
for (let adjNode of graph.nodes[newNode]){
if (!visited.has(adjNode)){
q.unshift(adjNode);
visited.add(adjNode);
}
}
}
}
bfs(g,2);
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.