Which data structure is used for BFS in graphs?

Concept — the frontier's removal order is the traversal order. Breadth-first search visits the vertices of a graph in non-decreasing order of their distance from the source: every vertex at distance d is visited before any vertex at distance d + 1. Any such search keeps its discovered-but-not-yet-explored vertices in a frontier container, and the order in which that container releases elements is exactly the order in which the search explores them. Level-by-level exploration therefore requires a container that releases elements in the same order they arrived — a first-in, first-out (FIFO) discipline.

Application — the standard BFS loop. The classical formulation (CLRS, Introduction to Algorithms, §22.2) holds the frontier in a FIFO container:

1. Mark the source s as visited, set dist(s) = 0, and insert s into the frontier.

2. While the frontier is not empty, remove the element at its front and call it u.

3. For every neighbour v of u that is not yet visited, mark v visited, set dist(v) = dist(u) + 1, and insert v at the rear of the frontier.

4. Stop when the frontier empties; every vertex reachable from s has then been visited exactly once, so the run costs O(V + E) time and O(V) extra space.

Why FIFO produces levels. Vertices at distance 1 are inserted while the source is being explored, and vertices at distance 2 only while a distance-1 vertex is being explored. Because insertion is at the rear and removal is from the front, everything inserted at distance 1 leaves the container before anything inserted at distance 2; the frontier therefore holds vertices of at most two consecutive distances and the visit order is level by level. The structure defined by exactly this insert-at-rear, remove-from-front behaviour is the queue, so a queue is the data structure used for BFS.

Cross-check — trace on a small graph. Take the edges A–B, A–C, B–D, C–D, D–E with source A; the front of the queue is written first.

The visit order A, B, C, D, E gives dist(A) = 0, dist(B) = 1, dist(C) = 1, dist(D) = 2 and dist(E) = 3 — every level finished before the next one starts, which is what BFS must produce. Holding the same frontier in a last-in, first-out container instead changes the order to A, C, D, E, B: a deep descent along one branch, not a level sweep.

Contrast with the other structures named.

• A stack releases the most recently inserted vertex, so the walk pushes on along one branch and backtracks only at a dead end — that is depth-first search rather than a level sweep.

• A tree is a hierarchy of parent-child links, a graph shape rather than an insertion-order container; BFS in fact produces such a hierarchy (the BFS tree) as its output, so it is a result of the traversal and not the mechanism that drives it.

• A hash table fixes each entry's position from its key and keeps no order among entries; BFS commonly uses one as the visited set for fast membership tests, but it cannot supply the ordering the level sweep depends on.

Result. The frontier of a breadth-first search is held in a queue.