Finding the Shortest Path with Breadth-First Search (BFS)
Problem Setup
Scenario:Find a path from the start node S to the goal node G by exploring the graph level by level.
Given:A directed graph with S as the start node and G as the goal node. S branches to A and B, with further connections through C, D, and E before reaching G.
Task:Apply Breadth-First Search using a FIFO queue, record the node explored at each step, and determine the path from S to G along with the number of edges in that path.
Need a quick refresher? Review Breadth-First Search theory
Search Graph
Arrows show which direction each connection can be followed. Multiple routes can lead to the same node, but BFS records its parent when the node is first discovered.
Step-by-Step FIFO Queue Resolution
| Step | Open List (Queue) | Evaluating Node | Closed List (Visited) |
|---|---|---|---|
1 | [ S ] | S | [ ] |
2 | [ A, B ] | A | [ S ] |
3 | [ B, C, D ] | B | [ S, A ] |
4 | [ C, D, E ] | C | [ S, A, B ] |
5 | [ D, E, G ] | D | [ S, A, B, C ] |
6 | [ E, G ] | E | [ S, A, B, C, D ] |
7 | [ G ] | G | [ S, A, B, C, D, E ] |
8 | [ ] | Goal Reached | [ S, A, B, C, D, E, G ] |
Final Answer
The search reaches the goal through the shortest path found by the breadth-first traversal:
Shortest path:S → A → C → G
Total path steps:3
G is first discovered through C, so BFS records C as its parent. Although D also connects to G, this does not replace the existing parent. The resulting path has 3 edges, the minimum possible in this graph.
Exam Takeaway
- Maintain FIFO order: Add newly discovered neighbors to the back of the queue. Nodes already waiting must be processed first, even if the new neighbors were discovered from the current node.
- Mark nodes when discovered, not when processed: A node may be reachable through multiple parents. Recording it when first enqueued prevents duplicate entries and preserves the first-discovered shortest path.
- Count edges, not visited nodes: BFS finds a path with the fewest edges in an unweighted graph. The traversal may process many nodes that are not part of the final path, so reconstruct the path using parent links before counting its steps.