Breadth-First and Depth-First Search

Every graph algorithm in this vault — shortest paths, spanning trees, flow, connectivity — is built from a small number of ways to systematically visit every reachable vertex exactly once. Breadth-first search (BFS) and depth-first search (DFS) are the two fundamental traversal strategies, differing only in which vertex to explore next: BFS explores layer by layer outward from a source (via a queue), while DFS plunges as deep as possible before backtracking (via a stack, or equivalently recursion). This note builds both, proves BFS gives shortest paths in edge count on unweighted graphs, and introduces DFS's discovery/finish times — the bookkeeping Topological Sort is built on directly.