On this page
Description
Breadth-first search (BFS) and depth-first search (DFS) are the two ways to visit every node you can reach in a graph. Almost every graph question starts with one of them: is B reachable from A, how many separate groups are there, what's the fewest-hop route? A graph has no root and may have cycles or several separate pieces. A cycle leads back to a node you've already seen, so both traversals keep a visited set.
We'll go from simple to more technical:
- The pattern: DFS, BFS, and an outer loop that covers every component.
- A second flavor: BFS distances and rebuilding the path.
- Where traversals run in production (reachability, linked accounts, garbage collection).
- What breaks it, and how to choose between BFS and DFS.
The approach
Take six nodes with edges 0-1, 0-2, 1-3, 2-3 and 4-5. A BFS from 0 runs like this:
| Take | New neighbors (marked now) | Queue after |
|---|---|---|
| 0 | 1, 2 | 1, 2 |
| 1 | 3 (0 is already marked) | 2, 3 |
| 2 | none (0 and 3 are marked) | 3 |
| 3 | none | empty |
Nodes 4 and 5 are never reached: they form a second component. An outer loop over every node starts a fresh traversal from 4, so the graph has 2 components.
Java
// DFS: go as deep as possible along one path, then back up
void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int next : adj.get(node)) {
if (!visited[next]) dfs(next, adj, visited);
}
}
// BFS: visit everything 1 edge away, then everything 2 edges away, ...
void bfs(int start, List<List<Integer>> adj, boolean[] visited) {
Deque<Integer> queue = new ArrayDeque<>();
visited[start] = true; // mark on discovery...
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : adj.get(node)) {
if (!visited[next]) {
visited[next] = true; // ...not when it's taken out of the queue
queue.add(next);
}
}
}
}
// Either traversal reaches one component; the outer loop covers them all
int components = 0;
for (int v = 0; v < n; v++) {
if (!visited[v]) { components++; dfs(v, adj, visited); }
}
Python
from collections import deque
# DFS: go as deep as possible along one path, then back up
def dfs(node: int, adj: list[list[int]], visited: list[bool]) -> None:
visited[node] = True
for nxt in adj[node]:
if not visited[nxt]:
dfs(nxt, adj, visited)
# BFS: visit everything 1 edge away, then everything 2 edges away, ...
def bfs(start: int, adj: list[list[int]], visited: list[bool]) -> None:
queue = deque([start])
visited[start] = True # mark on discovery...
while queue:
node = queue.popleft()
for nxt in adj[node]:
if not visited[nxt]:
visited[nxt] = True # ...not when it's taken out of the queue
queue.append(nxt)
# Either traversal reaches one component; the outer loop covers them all
components = 0
for v in range(n):
if not visited[v]:
components += 1
dfs(v, adj, visited)
Each node is expanded once, so each edge is looked at a constant number of times: O(V + E) with adjacency lists. Each fresh start in the outer loop explores one component, so counting fresh starts counts components.
A second flavor: BFS distances and the path itself
BFS finishes every node at distance d before it touches distance d + 1. So when it first discovers a node, it has found a fewest-edge path to it. In the graph above, 1 and 2 are at distance 1 and 3 is at distance 2. Record the distance and the node you came from at discovery, and you can rebuild the path:
Java
int[] dist = new int[n], parent = new int[n];
Arrays.fill(dist, -1); // -1 = not discovered; doubles as visited
Arrays.fill(parent, -1);
dist[src] = 0;
queue.add(src);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; queue.add(v); }
}
}
// path: walk parent[] back from dst to src, then reverse
Python
dist = [-1] * n # -1 = not discovered; doubles as visited
parent = [-1] * n
dist[src] = 0
queue = deque([src])
while queue:
u = queue.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
parent[v] = u
queue.append(v)
# path: walk parent[] back from dst to src, then reverse
DFS gives no such guarantee: its first path to a node can be long. With weighted edges, fewest edges isn't cheapest either. That's Dijkstra's job.
Where you'll see it
Reachability, connected groups (accounts that share a device) and fewest-hop routes (a crawler's link depth) are all BFS or DFS. Garbage collectors find live objects the same way, marking everything reachable from the roots.
Which tool for which job?
| You need | Use |
|---|---|
| Is B reachable from A? | either traversal from A |
| Count or label connected groups | an outer loop over unvisited nodes, one traversal each |
| Fewest edges between two nodes | BFS, recording distance and parent at discovery |
| Paths, cycles or an ordering | DFS |
| Weighted shortest paths | Dijkstra, not BFS |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No visited check | loops forever on a cycle | mark every node you reach |
| Marking on dequeue, not on enqueue | 19,901 queue insertions instead of 200 on a complete graph | mark when you enqueue |
| One traversal for the whole graph | other components are silently skipped | an outer loop over all nodes |
| Recursive DFS on a deep graph | stack overflow (Python at about 1,000 frames) | an explicit stack |
list.pop(0) as a Python queue | BFS turns quadratic | collections.deque and popleft() |
| DFS for shortest paths | finds a path, not the fewest-edge one | BFS |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A BFS marks a node visited only when it's dequeued (and skips it if it was already visited). Is the result wrong, and what does it cost?
Show answer
The order still comes out right. But until a node is dequeued, every edge into it adds another copy: 19,901 insertions instead of 200 on a complete graph of 200 nodes. Marking on enqueue keeps each node in the queue once.
2. Which uses less memory, DFS or BFS?
Show answer
It depends on the shape. DFS keeps the current path, so a long chain costs O(V). BFS keeps the frontier, so a star with one hub costs O(V), where DFS needs two frames. Both are O(V) in the worst case.
3. How do you count connected components with a traversal?
Show answer
Loop over every node, and start a fresh traversal from each one still unvisited, adding one to the count. The traversal marks what it reaches, so nothing is counted twice.
Key takeaways
- Every traversal needs a visited set, and marks a node when it first discovers it.
- One traversal covers one component; an outer loop over unvisited nodes covers the rest, and counts them.
- BFS discovers nodes in order of edge distance, so dist and parent recorded at discovery give fewest-edge paths.
- Both are O(V + E) time and O(V) memory in the worst case.