Exploring a Network
Once data is a graph, the fundamental operation is traversal: systematically visiting vertices by following edges. Two strategies dominate, differing only in the order they explore — and that order comes directly from the data structure each uses.
Breadth-first search (BFS) explores level by level: it visits all neighbors of the start, then all their unvisited neighbors, rippling outward. It uses a queue (FIFO) to remember what to visit next. On an unweighted graph, BFS finds the shortest path (fewest edges) from the start to every reachable vertex — a key property.
Depth-first search (DFS) plunges as deep as possible along one path before backtracking. It uses a stack (LIFO) — often the call stack, via recursion. DFS is natural for exploring all of a structure, detecting cycles, and topological sorting of a dependency graph.
Both visit each vertex and edge a constant number of times, so both run in . Both must track visited vertices to avoid revisiting and looping forever in a cyclic graph — a common bug is omitting the visited set.
For weighted graphs where edges have costs, shortest paths need more: Dijkstra's algorithm greedily expands the nearest unsettled vertex using a priority queue (heap), finding shortest paths when weights are non-negative. It is a beautiful synthesis — a graph, a greedy choice, and a heap working together.
Common pitfall: forgetting the visited set. In a graph with cycles, a traversal that does not mark vertices as visited will follow edges around a cycle forever (or explode exponentially re-exploring). Every graph traversal must track visited vertices to guarantee it terminates and each vertex is processed once.
One graph explored two ways: BFS rippling outward in numbered accent rings from the start (queue), and DFS plunging along one deep path then backtracking (stack) — the queue-vs-stack order made visual.