Question: Which of the following is useful in traversing a given graph by breadth first search?
A Stacks
B Set
C List
D Queue
Answer: Queue
| Data Structure | Description and Suitability for BFS Traversal |
| Queue | · Queues are the primary data structure used in BFS traversal. · They follow a First-In-First-Out (FIFO) order, which is ideal for exploring neighbor nodes at the current depth level before moving to nodes at the next depth level. · Queues help maintain the order of node processing required for BFS. |
| Stack | · Not commonly used in BFS traversal. · Stacks follow a Last-In-First-Out (LIFO) order, which is not sui <table for BFS, where nodes at the current level need to be explored before moving to the next level. · A stack can be used in certain scenarios for other traversal algorithms like Depth-First Search (DFS). |
| Set | · Sets are used for maintaining unique elements and may not be the primary data structure for BFS traversal. · Sets can be used to keep track of visited nodes in BFS to prevent revisiting, they are typically combined with a queue as an auxiliary data structure to ensure proper BFS traversal. |
| List | · Lists alone are not the primary choice for BFS traversal. · They lack the specific ordering required for BFS, where nodes at the current level need to be processed before moving to the next level. · Lists can be used to represent adjacency lists in graph representations, aiding in BFS implementation when combined with a queue. |