Loading...
Breadth-First Search explores a graph level by level. Starting from a source node, it visits all neighbors, then neighbors of neighbors, ensuring the first time a node is discovered is via the shortest number of edges from the source (in unweighted graphs).
Expands frontier layer by layer
First discovery gives min edge count
FIFO ensures level ordering
Maintain a queue of the current frontier. Dequeue a node, process it, and enqueue all undiscovered neighbors. Mark nodes when enqueued to avoid duplicates. Track distance by storing level = parent level + 1.