During breadth-first search, the frontier is the queue of graph vertices discovered but not yet visited. It forms the expanding perimeter of the search. section 14.3.2
Maintain the frontier through these operations:
- Initialize it with the source vertex. section 14.3.2
- Dequeue the next vertex, then inspect its adjacency list. section 14.3.2
- When an undiscovered neighbor is found, assign its distance and enqueue it at the tail. section 14.3.2
- Use a regular queue because discovery order matches increasing distance from the source; a priority queue is unnecessary. section 14.3.2
BFS frontier update
The pseudocode dequeues v, explores each outgoing edge, and enqueues an undiscovered destination u after setting distance[u] to distance[v] + 1 and recording v as its parent.
