Graph Traversal
Interactive visualizations for Chapter 8 of the Ricerca Operativa notes
The Running Graph
We work with a directed graph of 7 nodes and 11 arcs throughout this chapter.
- Nodes: s, a, b, c, d, e, t
- Arcs (with weights): s→a(4), s→b(2), a→c(5), a→d(1), b→a(8), b→d(3), c→e(3), c→d(2), d→e(6), d→t(9), e→t(1)
Breadth-First Search (BFS) from s
BFS explores the graph level by level, using a FIFO queue. We treat all arcs as undirected for the traversal (so b–a counts even though the arc b→a exists).
| Step | Dequeue | Enqueue | Queue after | Visited after |
|---|---|---|---|---|
| 0 | — | s | [s] | {} |
| 1 | s | a, b | [a, b] | {s} |
| 2 | a | c, d | [b, c, d] | {s, a} |
| 3 | b | (d already queued) | [c, d] | {s, a, b} |
| 4 | c | e | [d, e] | {s, a, b, c} |
| 5 | d | — | [e] | {s, a, b, c, d} |
| 6 | e | t | [t] | {s, a, b, c, d, e} |
| 7 | t | — | [] | {s, a, b, c, d, e, t} |
BFS Layers
BFS naturally partitions the nodes into distance layers from the source.
BFS Order Summary
Depth-First Search (DFS) from s
DFS follows the directed arcs and goes as deep as possible before backtracking, using a LIFO stack (or recursion).
Adjacency order used: s→[a,b], a→[c,d], b→[a,d], c→[e,d], d→[e,t], e→[t]
| Call stack | Action |
|---|---|
| [s] | Visit s, push a then b (explore a first) |
| [s,a] | Visit a, push c then d |
| [s,a,c] | Visit c, push e then d |
| [s,a,c,e] | Visit e, push t |
| [s,a,c,e,t] | Visit t – dead end, backtrack |
| [s,a,c] | c→d not yet visited, visit d |
| [s,a,c,d] | d→e visited, d→t visited – backtrack |
| [s,a] | a→d visited – backtrack |
| [s] | s→b not yet visited |
| [s,b] | Visit b – b→a visited, b→d visited – backtrack |
| [] | Done |
DFS order: s → a → c → e → t → d → b
BFS vs DFS Comparison
Key differences:
| Property | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack (LIFO) / recursion |
| Traversal order | Level by level | As deep as possible first |
| Shortest path (unweighted) | Yes (by hop count) | No |
| Memory (worst case) | O(V) – wide graphs | O(V) – deep graphs |
| Finds cycles | Yes | Yes |
| Topological sort | No (directly) | Yes (reverse post-order) |
Applications
BFS – Shortest Hop Distance from s
In an unweighted graph, BFS gives the minimum number of hops from the source to every reachable node.
DFS – Topological Ordering (Reverse Post-Order)
For a DAG, DFS produces a topological order by reversing the order in which nodes finish (post-order). Every arc u→v appears with u before v.
The topological order s, b, a, c, d, e, t respects all arc directions: for every arc u→v in the graph, u appears before v in this ordering. This property is essential for dynamic-programming algorithms on DAGs (e.g., longest/shortest path in a DAG).