In Breadth-First Search (BFS), what data structure is

Solution

Breadth-First Search (BFS) uses a queue to keep track of the nodes to be explored. A queue follows the First-In-First-Out (FIFO) principle, ensuring that nodes are explored level by level. Nodes are added to the queue when they are encountered, and the front node is explored first before moving to its children. Option A (Stack) is incorrect because stacks follow a Last-In-First-Out (LIFO) order, which is used in Depth-First Search (DFS), not BFS. Option B (Priority queue) is incorrect because BFS explores nodes level by level without prioritizing nodes based on any criteria. Option D (Linked list) is incorrect because a linked list does not naturally follow FIFO principles unless implemented as a queue. Option E (Binary heap) is incorrect because a binary heap is used in algorithms like Dijkstra’s shortest path, not BFS traversal.