Graph Traversal (BFS & DFS)
A graph connects nodes with edges in any pattern, and BFS explores it level by level while DFS dives down one path at a time.
Loading visual…
Definition
A graph is a set of nodes (often called vertices) connected by edges, and unlike a tree, a graph places no restriction on how those edges connect: a node can have any number of neighbors, edges can point both ways or just one way, and following edges can lead back to a node that was already visited, forming a cycle. A common way to represent a graph in code is an adjacency list, an object or map where each node's key holds an array of the neighbors it connects to directly. Traversing a graph means visiting every reachable node, and because cycles are allowed, every traversal needs a visited set to avoid processing the same node twice or looping forever. Breadth-first search (BFS) uses a queue: it visits the starting node, enqueues its neighbors, then repeatedly dequeues a node and enqueues whichever of its neighbors have not been seen yet, which visits every node one edge away before any node two edges away, the same level-by-level shape as a tree's level-order traversal. Depth-first search (DFS) uses a stack, whether an explicit one or the implicit call stack from recursion: it follows one path as far as it can before backtracking, which is well suited to questions like whether a path exists between two nodes at all, rather than the shortest one. Because BFS explores in order of distance, it is the standard way to find the shortest path in an unweighted graph.
Examples
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
return order;
}
const graph = { A: ["B", "C"], B: ["A", "D"], C: ["A", "D"], D: ["B", "C", "E"], E: ["D"] };
bfs(graph, "A"); // ["A", "B", "C", "D", "E"]Each node is enqueued the first time it is seen, so the queue drains in order of distance from A, visiting B and C (one edge away) before D (two edges away) and E (three edges away).
function dfs(graph, node, visited = new Set(), order = []) {
visited.add(node);
order.push(node);
for (const next of graph[node]) {
if (!visited.has(next)) dfs(graph, next, visited, order);
}
return order;
}
dfs(graph, "A"); // ["A", "B", "D", "C", "E"]The recursive call dives into the first unvisited neighbor completely, using the call stack as the stack, before ever returning to try A's other neighbor, C, which is why the order differs from BFS.
function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
const order = [];
while (stack.length) {
const node = stack.pop();
if (visited.has(node)) continue;
visited.add(node);
order.push(node);
for (const next of graph[node]) stack.push(next);
}
return order;
}Popping from the end of an array, instead of shifting from the front, is what turns this into a depth-first walk: the most recently discovered node is explored next.
Common mistakes
- Forgetting the visited set and re-processing (or infinitely looping on) a node that a cycle leads back to.
- Marking a node visited when it dequeues instead of when it enqueues in BFS, which can enqueue the same node multiple times.
- Reaching for DFS when the shortest path is what actually matters; only BFS guarantees the fewest edges on an unweighted graph.
Key takeaways
- A graph allows any pattern of connections, including cycles, so traversals need a visited set that a tree traversal does not.
- BFS uses a queue and explores level by level, finding the shortest path in an unweighted graph.
- DFS uses a stack, explicit or via recursion, and dives down one path before backtracking.
You need the fewest number of edges between two nodes in an unweighted graph. Which traversal guarantees that?
Where you see this
- Finding the shortest number of hops between two people in a social network (BFS).
- Web crawlers exploring links from a page, or dependency resolvers walking a package graph.
- Checking whether a maze or map has a path between two points at all (DFS).
- Detecting cycles in a graph, such as a circular dependency between modules.