Breadth-First Search (BFS)

Math for CS · Axiom Academy

LESSON Breadth-First Search (BFS) Level-by-level exploration and shortest paths in unweighted graphs Breadth-First Search explores a graph outward from a source vertex in concentric "waves." It visits all vertices at distance 1 before any vertex at distance 2, all at distance 2 before any at distance 3, and so on. BFS Guarantee: When BFS first discovers a vertex , the path it used has the fewest possible edges from to . This is the shortest path in any unweighted graph. The secret is a simple data structure: a FIFO queue . Vertices discovered earlier get explored earlier, enforcing the level-by-level order. GRAY — discovered but not fully explored (in the queue) BLACK — fully explored (all neighbors checked) Note: The parent[] array lets you reconstruct the actual shortest path by following parent pointers from any vertex back to . Consider a graph with vertices and edges . Start BFS from vertex . The BFS tree has edges: , , , , . Every vertex's dist value equals its shortest distance from . Each vertex is enqueued and dequeued at most once: . Each edge is examined at most twice (once from each endpoint in an undirected graph): . The queue, color array, distance array, and parent array each use space. This is optimal: you cannot find shortest paths without examining the entire graph, which requires time. Shortest-Path Property: For every vertex reachable from , , where is the minimum number of edges on any -to- path.

This is the written version of the interactive lesson above. See the full Math for CS course.