Question

The data structure required for Breadth First Traversal on a graph is?

(a) Stack

(b) Array

(c) Queue

(d) Tree

My doubt is from Queue Operations topic in section Abstract Data Types of Data Structures & Algorithms I

The question was posed to me in quiz.

Answer 1

Right choice is (c) Queue

Best explanation: In Breadth First Search Traversal, BFS, starting vertex is first taken and adjacent vertices which are unvisited are also taken. Again, the first vertex which was added as an unvisited adjacent vertex list will be considered to add further unvisited vertices of the graph. To get the first unvisited vertex we need to follows First In First Out principle. Queue uses FIFO principle.