JavaScript graphs: BFS, DFS, and path existence
A graph is a set of nodes joined by edges. An adjacency list stores the neighbours of each node, here in a Map from a node name to an array. Breadth-first search (BFS) explores layer by layer with a queue and finds the fewest-edges path. Depth-first search (DFS) follows one path as far as it can before backing up, with recursion or an explicit stack.
JavaScript
const graph = new Map([
["A", ["B", "C"]],
["B", ["D"]],
["C", ["D", "E"]],
["D", ["F"]],
["E", ["F"]],
["F", []],
["X", ["Y"]],
["Y", []],
]);
function bfs(start) {
const order = [];
const seen = new Set([start]);
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const next of graph.get(node)) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return order;
}
function dfs(node, seen = new Set(), order = []) {
seen.add(node);
order.push(node);
for (const next of graph.get(node)) {
if (!seen.has(next)) {
dfs(next, seen, order);
}
}
return order;
}
console.log("bfs: " + bfs("A").join(" "));
console.log("dfs: " + dfs("A").join(" "));
console.log("A reaches F: " + dfs("A").includes("F"));
console.log("A reaches Y: " + dfs("A").includes("Y"));