A queue is a first-in, first-out (FIFO) data structure: the element waiting longest is removed first. Breadth-first search uses a queue to hold states awaiting exploration, expanding one state and adding its successors to the back. section 3.3.1
In breadth-first search, the queue supports a repeated cycle:
- Initialize it with the source node. section 3.3.1
- Dequeue the next state and add it to the explored set. section 3.3.1
- Expand the state and enqueue successors that are neither explored nor already waiting. section 3.3.1
8-puzzle search
For the 8-puzzle, each queue entry represents a board configuration. BFS removes the oldest configuration, generates legal blank-tile moves, and places new configurations at the back, producing layer-by-layer exploration. section 3.3.1
Algorithm 3.1 Breadth-first search (BFS)
Inputs: Source node, Destination node Output: Route from source to destination Initialize queue ← a FIFO initialized with source node Initialize explored ← empty Initialize found ← False While queue is not empty and found is False do Set node ← queue.dequeue() Add node to explored For child in node.expand() do If child is not in explored and child is not in queue then If child is destination then Update route ← child route() Update found ← True Add child to queue Return route
Use the BFS pseudocode to trace queue initialization, dequeue operations, successor checks, route detection, and termination. section 3.3.1
FIFO ordering favors shallow, earlier-generated states, but it does not by itself evaluate route optimality. Queue insertion and removal are listed as constant-time operations in the complexity reference. section 3.3.1
