Which data structure is most commonly used to implement Breadth-First Search (BFS) of a graph?

Options

  • A. Stack
  • B. Queue
  • C. Binary Search Tree
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. Queue

Detailed Explanation

Breadth-First Search (BFS) uses a queue to process vertices level by level. When a vertex is visited, its unvisited adjacent vertices are inserted into the queue. The vertex at the front is then processed first. This FIFO behavior ensures that vertices closer to the starting vertex are explored before vertices at greater distances. In contrast, DFS commonly uses a stack or recursion.