JavaScript graphs: BFS, DFS, and path existence
Store a graph as a Map of neighbour lists and search it breadth-first and depth-first.
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"));bfs: A B C D E F dfs: A B D F C E A reaches F: true A reaches Y: false
Explanation
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.
Both searches keep a Set of visited nodes so that cycles do not cause endless loops. Checking whether a path exists between two nodes is a search from one to see if it reaches the other. The order in which neighbours are listed decides the visiting order, so the two traversals below visit the same nodes in different orders.
Explore the dry run
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"));Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Each node maps to the list of nodes it points to. X and Y form a separate piece. | — | — | |
| BFS starts with the start node in a queue. | queue = [A] | — | |
| A node is marked when it is queued, so it never enters the queue twice. | queue = [A] | — | |
| BFS visits A, then its neighbours B and C, then the next layer D and E, then F. | queue = [A] | bfs: A B C D E F | |
| DFS goes A, B, D, F to the bottom, backs up, and then visits C and E. | queue = [A] | bfs: A B C D E F dfs: A B D F C E | |
| F is reachable. | queue = [A] | bfs: A B C D E F dfs: A B D F C E A reaches F: true | |
| Y is in a different component, so it is not reachable from A. | queue = [A] | bfs: A B C D E F dfs: A B D F C E A reaches F: true A reaches Y: false |
Cost and common mistakes
BFS and DFS are O(V + E).
- queue.shift() is O(n) on a large array, so BFS on a large graph needs a proper queue (for example with a head index).
- Without a visited set, a graph with a cycle makes both searches loop forever.
- Recursive DFS can exceed the call stack on a long chain of nodes. An explicit stack avoids it.
Try it yourself
How would you get the shortest path between two nodes?
Reveal answer and reasoning
Run BFS and record each node's parent when it is first reached, then follow the parents back from the goal to the start.