BFS Algorithm

Breadth-first search explores a graph one distance layer at a time. Store edges in an adjacency list, place the start vertex in a FIFO queue, and mark it visited immediately. Repeatedly remove the front vertex, process it, then inspect all adjacent vertices. For each unvisited neighbor, mark it, optionally store its parent and distance, and append it to the queue. The core invariant is that queue order is nondecreasing distance from the source, which explains shortest path length in an unweighted graph. If the graph can be disconnected and the operation is a full traversal, wrap the BFS in a loop over all vertices. For a grid, treat each valid cell as a vertex and check bounds before enqueueing. Test cycles, a single vertex, no edges, duplicate edges, and directed versus undirected input. Time is O(V plus E) and auxiliary space is O(V) with an adjacency list. Do not use a stack: that changes the traversal to DFS.