Network Traversal: BFS vs DFS
Once data is a graph, traversal (systematically visiting vertices along edges) is the fundamental operation. Two strategies dominate, differing only in the data structure and order of exploration.
| Strategy | Data Structure | Exploration Pattern | Key Use Case |
|---|---|---|---|
| BFS | Queue (FIFO) | Ripples outward, level by level | Shortest path on unweighted graphs |
| DFS | Stack (LIFO) | Plunges deep, then backtracks | Topological sorting & cycle detection |
Both strategies visit each vertex and edge a constant number of times, running in time.
Weighted Graphs & Pitfalls
For weighted graphs where edges carry costs, standard BFS fails. Dijkstra's algorithm greedily expands the nearest unsettled vertex using a priority queue (heap), finding shortest paths when weights are non-negative.
Common pitfall: Forgetting the visited set. In a cyclic graph, omitting this causes infinite loops or exponential re-exploration.
Every graph traversal must track visited vertices to guarantee termination and process each vertex exactly once.