Chapter 20: Elementary Graph Algorithms: BFS, DFS, and Topological Sort

Breadth-first search (BFS) explores a graph in expanding waves outward from a source vertex s using a queue, coloring vertices white, gray, and black to track discovery state, and recording each vertex's shortest hop-count distance v.d and predecessor v.π — building a breadth-first tree that encodes shortest paths and running in O(V + E) time with an adjacency list. Depth-first search (DFS) instead dives as deep as possible before backtracking, tracking discovery and finish timestamps for each vertex and producing a depth-first forest; it runs in Θ(V + E) time and classifies edges in directed graphs as tree, back, forward, or cross edges — with undirected graphs producing only tree and back edges. Topological sort leverages DFS on a directed acyclic graph (DAG) to produce a linear ordering of vertices consistent with all directed edges, by inserting each vertex at the front of a list as it finishes, yielding a valid topological order in Θ(V + E) time provided no back edges are found. Finally, strongly connected components (SCCs) — maximal subsets where every vertex is mutually reachable — are identified by Kosaraju's algorithm in Θ(V + E) time through three steps: running DFS on the original graph to record finish times, constructing the transpose graph G^T with all edges reversed, and running DFS on G^T in decreasing order of finish times, where each resulting DFS tree corresponds to exactly one SCC.