ISRO2017-17

Question

Which of the following data structure is useful in traversing a given graph by breadth first search?

• A. Stack
• B. Queue
• C. List
• D. None of the above

Comments

But sir, both queue and list can be used for performing BFS.

---

@Sir Arjun, D Graph being a Directed, With Loops, A simple one or Non Directed???. :D :)

Answer 1

Breadth-first search  uses a Queue data structure.

https://en.wikipedia.org/wiki/Breadth-first_search#More_details

Comments

But a list can also be used to implement BFS efficiently. We can list to design a queue

---

when multiple option is given then go for Best ..Here Queue is best B/C of FIFO property.

---

We use List for the efficient representation of the Graph as it takes Θ(V+E) memory and as BFS scans across the frontier of the graph we actually use Queue data structure for traversing...

Answer 2

BFS uses queue data structure

DFS  uses   stack data structure  

to implement efficiently

Answer 3

Queue is used to implement traveral in Breadth First Search.

Stack is used to implement traversal in Depth First Search.

Answer 4

Option b queue