Questions: Queue Applications: Level-Order Traversal and Breadth-First Search

Question 1

In BFS, a node is discovered via two different paths simultaneously. Which path is guaranteed to be shortest?

• A. The path that was enqueued first, because FIFO ordering ensures earlier-discovered paths are shorter
• B. There is no guarantee — BFS explores all paths and picks the shortest afterward
• C. The path through the node with the fewest neighbors, because it processes faster
• D. Both paths are equally short, because BFS expands in all directions simultaneously

Answer: (A)

FIFO ordering is the mechanism that makes BFS guarantee shortest paths. When a node is enqueued via one path, all nodes at the same distance have already been enqueued before any node at a greater distance. So the first time BFS reaches a node, it is necessarily via a shortest path — any later arrival would come from a longer route still waiting in the queue. This is not true of DFS, which dives deep along one branch and may reach a node via a long path before exploring a shorter one.

Question 2

You modify BFS by replacing the queue with a stack. What traversal order results?

• A. The same level-by-level BFS order, because the graph structure determines traversal
• B. Depth-first search — the stack causes deep exploration of one branch before backtracking
• C. Random order — a stack does not preserve any meaningful traversal structure
• D. Reverse BFS — nodes are visited in the opposite order from normal BFS

Answer: (B)

The choice between queue and stack is the entire difference between BFS and DFS. A queue's FIFO discipline ensures that neighbors enqueued earlier (closer to the source) are processed before neighbors enqueued later (farther away), producing level-by-level exploration. A stack's LIFO discipline does the opposite: the most recently enqueued neighbor is processed first, driving exploration as deep as possible along one path before backtracking. The data structure, not the graph, determines the traversal order.

Question 3

In BFS on a graph, a node should be marked visited when it is dequeued, not when it is enqueued, so that most processing happens before the node is locked out.

• T. True
• F. False

Answer: False

This is exactly backwards and is one of the most common BFS implementation bugs. Nodes must be marked visited at enqueue time. If you wait until dequeue, the same node can be enqueued multiple times before it is ever dequeued — once for each neighbor that discovers it. In graphs with cycles this causes infinite loops; in any graph it causes redundant processing and incorrect results. Marking at enqueue ensures each node enters the queue at most once, which is what guarantees O(V + E) time complexity.

Question 4

BFS guarantees that the first time any node is reached, it is via a shortest path from the source.

• T. True
• F. False

Answer: True

This is the fundamental correctness property of BFS in unweighted graphs. Because the queue processes nodes in non-decreasing order of distance from the source, any node reached at distance d has had all nodes at distances 0, 1, ..., d-1 already processed. No shorter path to this node exists, because if one did, the node would have been discovered earlier. This property fails in weighted graphs (where Dijkstra's algorithm is needed) and in DFS (which may reach a node via a long path first).

Question 5

Explain why using a queue (rather than a stack or any other structure) is what makes BFS explore nodes level by level.

Model answer: A queue's FIFO discipline ensures that nodes are processed in the order they were discovered. When you enqueue a node's neighbors, those neighbors are added to the back of the queue. All nodes from the previous level are at the front and get processed first. Only after all nodes at distance k are dequeued — and their neighbors (at distance k+1) are enqueued — does the algorithm reach those next-level nodes. This is automatic: no explicit level-tracking is needed. A stack would process the most recently added neighbor first, diving into one branch deeply before returning to others, destroying the level-by-level property.

The queue is not a convenience — it is the mechanism. FIFO order corresponds directly to non-decreasing distance order. Any other ordering (LIFO, priority-based, random) would break the level invariant. This connection between FIFO and BFS is why queues appear in virtually every graph traversal problem that requires exploring nodes in order of their distance from a source.