Skip to content

Instantly share code, notes, and snippets.

@chasingmaxwell
Created October 16, 2020 21:12
Show Gist options
  • Save chasingmaxwell/3e36bc6d89c2c9cf08cb2ae6fd923ce6 to your computer and use it in GitHub Desktop.
Save chasingmaxwell/3e36bc6d89c2c9cf08cb2ae6fd923ce6 to your computer and use it in GitHub Desktop.
Implementation of breadth-first search in JavaScript.
// Implementation of breadth-first search in JavaScript.
function breadthFirstSearch(g, start, end) {
const queue = [[start]];
const visited = {};
while (queue.length > 0) {
const path = queue.shift();
const node = path[path.length - 1];
if (node === end) {
console.log("number of steps:", path.length - 1);
console.log("path:", path.join(" -> "));
return g[node];
}
visited[node] = true;
for (const neighbor of g[node]) {
const newSteps = [...path, neighbor];
if (!visited[neighbor]) {
queue.push(newSteps);
}
}
}
console.log(`No path from ${start} to ${end}`);
}
const graph = {
you: ["bob", "alice", "jake", "carol"],
bob: ["larry", "tony", "sara"],
alice: ["henry", "daryl", "tony"],
jake: ["bob"],
carol: ["daryl", "henry"],
larry: ["you", "alice", "tony"],
tony: ["henry", "you", "alice"],
sara: ["alice", "carol", "mary"],
mary: ["jake", "larry", "carol"],
henry: ["mary", "carol", "alice", "larry"],
daryl: ["tony"],
tony: ["alice"],
circleA: ["circleB"],
circleB: ["circleC"],
circleC: ["circleA"],
};
console.log(breadthFirstSearch(graph, "you", "mary"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment