Which data structure is central to BFS and explains why it explores a graph layer by layer?
AStack
BQueue
CPriority queue
DHash map
A queue's FIFO (first-in, first-out) ordering ensures that all nodes at distance d are fully processed before any node at distance d+1 is dequeued. A stack would produce DFS behavior instead, going deep before going wide.
Question 2 True / False
BFS finds the shortest weighted path between two nodes in any graph.
TTrue
FFalse
Answer: False
BFS finds the shortest path measured in number of edges (hops), which is only meaningful as a distance when all edges have equal weight. For weighted graphs where edges have different costs, Dijkstra's algorithm is required.
Question 3 Short Answer
Why must a node be marked as visited before it is enqueued, rather than after it is dequeued?
Think about your answer, then reveal below.
Model answer: If marking is deferred until dequeue, multiple neighbors can enqueue the same unvisited node before any of them is processed, causing the node to be visited multiple times. Marking before enqueue ensures each node enters the queue at most once.
This is one of the most common BFS implementation bugs. The visited check and the enqueue operation must be atomic from the graph's perspective: the moment you decide to enqueue a node, mark it so no other neighbor can also enqueue it.