Breadth-first search (BFS) is a blind graph-traversal technique that expands a search tree layer by layer: it explores every node at the current depth before moving to deeper nodes. It starts from a source node and continues until it finds a destination or exhausts the queue. section 3.2 section 3.3.1
Implement BFS with a first-in, first-out queue and an explored collection:
- Initialize the queue with the source, keep explored empty, and set found to false. section 3.3.1
- Dequeue the next node, mark it explored, and expand its successors. section 3.3.1
- Enqueue each successor that is neither explored nor already queued. section 3.3.1
- Stop when the destination is found, reconstructing its route, or when the queue becomes empty. section 3.3.1
Solving an 8-puzzle
Represent each puzzle configuration as a state, with the blank tile’s legal moves producing successors. BFS begins with the initial configuration, explores all one-move states, then all two-move states, and so on until the ordered goal state appears. A Python implementation checks solvability, calls BFS, and reports processing time, memory, explored states, and the resulting route. section 3.3.1
BFS can find a solution when each node has finitely many successors, but blind search does not use information about the search space and does not select the best route among feasible alternatives. Its queue and explored set can grow rapidly as depth increases, making time and memory practical constraints. section 3.2
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 compact pseudocode to trace queue updates, explored-state checks, successor expansion, and route reconstruction. section 3.3.1
