BFS & DFS
Die zwei grundlegenden Traversierungen: Breitensuche für kürzeste ungewichtete Wege und Ebenen, Tiefensuche für Zusammenhang - mit einer Visited-Menge gegen Zyklen.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Almost every graph problem is solved by one of two traversals: breadth-first search (BFS) or depth-first search (DFS). They differ in one choice - explore wide or explore deep - and that choice determines which problems each is good at. Master both, plus the one thing graphs need that trees don't: a visited set to avoid going in circles.
DFS: go deep
Depth-first search follows one path as far as it can before backtracking. It's naturally recursive (or uses an explicit stack), and it's the tool for connectivity, cycle detection, and "explore everything reachable":
// DFS from a start node - visits every reachable node once
void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
if (visited.contains(node)) return; // the crucial guard
visited.add(node);
process(node);
for (int next : graph.getOrDefault(node, List.of()))
dfs(next, graph, visited);
}BFS: go wide
Breadth-first search explores all neighbors at distance 1, then distance 2, and so on - level by level, using a queue. Its superpower: in an unweighted graph, the first time BFS reaches a node, it's via the shortest path:
// BFS shortest path (unweighted) - distance from start to every reachable node
Map<Integer, Integer> bfs(int start, Map<Integer, List<Integer>> graph) {
Map<Integer, Integer> dist = new HashMap<>();
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(start);
dist.put(start, 0);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : graph.getOrDefault(node, List.of())) {
if (!dist.containsKey(next)) { // not visited
dist.put(next, dist.get(node) + 1); // one step further
queue.offer(next);
}
}
}
return dist;
}The visited set: graphs aren't trees
Trees have no cycles, so tree traversal never revisits a node. Graphs can have cycles, so without a
visited set you'd loop forever. Marking each node visited when you first reach it guarantees every node
is processed once, making both BFS and DFS O(V + E) - each node and edge examined a constant number
of times.
Which one? Wide vs. deep
Use BFS when the problem involves shortest path, minimum steps, or levels in an unweighted graph ('fewest moves,' 'nearest,' 'level by level'). Use DFS for connectivity, cycle detection, topological sort, exploring all paths, or anything recursive on structure ('is everything connected,' 'find all islands,' 'does a path exist'). When either works, pick the one that reads more simply.
Two ways to explore a cave with many branching tunnels. Depth-first: pick a tunnel and follow it to its end, backtracking only when you hit a dead end, then trying the next unexplored branch - you go deep fast but wander far from the entrance. Breadth-first: check every tunnel one step in, then every tunnel two steps in, expanding a ring outward from the entrance - slower to reach the depths, but the first time you find the exit, you've found the shortest way out. And in both, you drop a chalk mark at every junction you've seen (the visited set), or you'd circle the same loops forever.
Given a grid maze with open cells and walls, find the fewest steps from start to exit. Explain why BFS (not DFS) is the right traversal, and what guarantees it returns the shortest path.
Why does BFS find the shortest path in an unweighted graph while DFS does not?
Key takeaways
- BFS (queue, explore wide) and DFS (stack/recursion, explore deep) solve nearly all graph problems.
- In an unweighted graph, BFS finds the shortest path - the first time it reaches a node is via the fewest edges.
- DFS suits connectivity, cycle detection, topological sort, and exploring all reachable nodes.
- Graphs can have cycles, so a visited set is essential - without it, traversal loops forever.
- Both traversals are O(V + E): each node and edge is examined a constant number of times.