How is a queue used in BFS (breadth-first search)?

In the BFS (Breadth-First Search) algorithm, a queue is used to store the vertices that need to be visited in the order they are discovered.

#The essence of BFS

The algorithm traverses the graph layer by layer: first all vertices at distance 1 from the starting one, then at distance 2, and so on.

#The role of the queue

1. First, the starting vertex is placed into the queue.
2. While the queue is not empty:

• a vertex is removed from the front of the queue (dequeue),
• all its unvisited neighbors are added to the end of the queue (enqueue).

3. This process continues until all reachable vertices have been processed.

#Why a queue specifically

A queue guarantees FIFO order: all vertices of one level are processed before the vertices of the next.

This is exactly why BFS traverses the graph layer by layer, unlike DFS, which uses a stack and goes deep.