Graph Traversal
Graph traversal is the process of visiting every vertex in a graph in a controlled, systematic order — no vertex is missed, and no vertex is visited twice. The two fundamental approaches are Breadth-First Search (BFS) and Depth-First Search (DFS) — each with distinct characteristics and use cases.
Why Traversal Matters#
Understanding traversal well means understanding the building block behind nearly every graph algorithm. Most graph problems reduce to one core idea: visit the right vertices in the right order.
Traversal is the foundation for:
- Finding paths between vertices
- Detecting cycles
- Finding connected components
- Topological sorting
- Shortest paths (unweighted)
- Solving puzzles and mazes
Breadth-First Search (BFS)#
BFS explores the graph level by level. It visits all vertices at distance 1 from the start, then all vertices at distance 2, and so on. Think of it as ripples spreading out from a stone dropped in water.
How BFS Works#
BFS Uses a Queue#
The key insight: a queue (FIFO) ensures we process vertices in order of their distance from the start. Because the queue is first-in first-out, all vertices at distance k are fully dequeued before any vertex at distance k+1 is touched — that is exactly what produces the level-by-level ordering.
Breadth-First Search (BFS)
Explore graph level by level using a queue
BFS Applications#
| Application | Description | Why BFS? |
|---|---|---|
| Shortest Path (Unweighted) | Find the minimum number of hops between two vertices | Guarantees shortest hop count because nearer vertices are always visited first |
| Level Order Traversal | Process vertices grouped by their distance from the source | Natural layer-by-layer structure matches BFS expansion order |
| Connected Components | Identify all vertices reachable from a given starting vertex | Exhaustively visits every vertex reachable via any path |
| Bipartite Check | Determine if the graph can be 2-colored (no two adjacent vertices share a color) | Alternating colors across BFS levels detects odd-length cycles that break bipartiteness |
| Web Crawling | Explore web pages breadth-first from a seed URL | Prioritises pages closest in link distance, avoiding deep rabbit holes early |
Depth-First Search (DFS)#
DFS explores as deep as possible before backtracking. It commits to one path, following it all the way to a dead end, then backtracks to the last junction and tries the next unexplored branch. Think of it as exploring a cave system: you go down one passage until you can go no further, then retrace your steps to the last fork and take the next tunnel.
How DFS Works#
DFS Uses a Stack (or Recursion)#
DFS can be implemented with an explicit stack or via recursion. Recursive DFS is often more readable, because the call stack itself acts as an implicit stack — each function call represents going one level deeper, and returning from a call is the backtrack step. For most use cases, the recursive version is perfectly fine. However, on graphs with very long chains, deep recursion can hit the runtime's stack-size limit and crash. The iterative version avoids this risk at the cost of slightly more bookkeeping.
Depth-First Search (DFS)
Explore graph by going as deep as possible before backtracking
DFS Applications#
| Application | Description | Why DFS? |
|---|---|---|
| Path Finding | Find any path (not necessarily shortest) between two vertices | Follows one route to its conclusion before trying alternatives — enough for existence checks |
| Cycle Detection | Detect cycles using back edges (an edge from a vertex to an ancestor in the DFS tree) | Back edges are only visible when tracking the recursion stack, which DFS naturally maintains |
| Topological Sort | Order vertices so every dependency comes before the vertex that depends on it (DAGs only) | Post-order DFS visits a vertex only after all its descendants are done, producing a valid topological order in reverse |
| Strongly Connected Components | Find maximal groups where every vertex can reach every other vertex | Algorithms like Kosaraju's and Tarjan's rely on DFS finish times to identify SCCs |
| Maze Solving | Explore all possible paths in a maze, backtracking on dead ends | Backtracking is built into DFS recursion — no extra bookkeeping needed |
| Tree Traversals | Pre-order, in-order, and post-order traversals are all DFS variants | DFS on a tree visits exactly the recursive sub-tree structure each traversal order exploits |
BFS vs DFS Comparison#
| Aspect | BFS | DFS |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Exploration | Level by level | As deep as possible first |
| Shortest Path | Yes (unweighted graphs) | No (finds a path, not shortest) |
| Space Complexity | O(V) — queue can hold an entire level at once, so a wide graph (many nodes per level) uses more memory | O(V) — stack depth equals the longest path explored, so a deep/linear graph uses more memory |
| Better For | Shortest path, level order, nearby nodes | Path existence, cycles, topological sort |
| Memory on Trees | O(width) — worst case for wide/complete trees | O(height) — better for balanced trees |
When to Use Which?#
Traversing All Components#
If a graph is disconnected, running BFS/DFS from a single vertex will silently miss any vertex that has no path to the starting point. For example, a dependency graph might have isolated packages with no dependents, or a social network might contain small isolated groups. The fix is to loop over every vertex and start a fresh traversal from any that have not been visited yet — each fresh start discovers one new connected component:
Complete Graph Traversal
Visit all vertices in a potentially disconnected graph
Reviewing AI-Generated Code#
AI assistants frequently produce traversal code that looks correct at a glance but contains subtle bugs — especially around when to mark a vertex as visited, which data structure to use, and whether the graph might be disconnected. These bugs are easy to miss in a quick review because the code often runs without errors on simple test inputs and only fails on edge cases. Here are the most common issues to check:
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Visited Tracking (BFS) | In BFS, mark a vertex as visited when it is added to the queue — not after it is dequeued | Marking after dequeue lets the same vertex enter the queue multiple times before being processed, causing redundant work |
| BFS vs DFS Choice | Queue for BFS, stack/recursion for DFS | Using a stack when shortest path is needed — a stack gives DFS order, not BFS |
| Shortest Path Claims | BFS guarantees shortest path only in unweighted graphs | Applying BFS to a weighted graph and assuming it finds the minimum-cost path |
| Disconnected Graphs | Loop over all vertices to start fresh traversals from any unvisited vertex | Only traversing from one start vertex, silently missing unreachable components |
| Infinite Loops | A visited set prevents revisiting vertices that have already been processed | Omitting the visited check on a graph with cycles causes the traversal to loop forever |
Common AI Pitfalls#
Traversal Implementation Bugs
Common mistakes AI makes in BFS and DFS
Questions to Ask AI#
When AI generates traversal code, push back with these questions before trusting the output:
- "Why did you choose BFS over DFS (or vice versa)?"
- "Does this handle disconnected graphs — graphs where some vertices have no path to the start?"
- "What's the time and space complexity?"
- "Could this cause a stack overflow for graphs with very long paths?" (for recursive DFS)
- "Does this correctly mark vertices as visited, and at what point?"
Summary#
| Concept | Key Takeaway |
|---|---|
| Graph Traversal | Systematically visit all vertices in a graph |
| BFS | Level by level using a queue — finds shortest path in unweighted graphs |
| DFS | Go deep first using stack/recursion — good for paths, cycles, topological sort |
| Time Complexity | Both are O(V + E) — visit every vertex and edge once |
| Space Complexity | O(V) for visited set and queue/stack |
| Connected Components | Run BFS/DFS starting from each unvisited vertex to find all components |
| Use BFS When | Need shortest path, level order, or nearby exploration |
| Use DFS When | Need any path, cycle detection, or topological ordering |
Master BFS and DFS and you'll have the foundation for almost every graph algorithm you'll encounter. When an AI generates a graph solution for you, knowing these two traversals is what lets you read the code critically, spot the edge cases, and verify that the logic is actually correct.