Micro-questions over the BFS module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. What is breadth-first search?
Answer
Expanding uniformly across every neighbour at the current distance before considering anything further away.
2. Give the physical metaphor.
Answer
Concentric ripples from a pebble dropped in water — the wave reaches everything one metre away before it reaches anything two metres away.
3. What is the entire difference between BFS and DFS?
Answer
The scheduling structure: BFS uses a queue (FIFO), DFS uses a stack (LIFO). Same code otherwise.
B. The vocabulary
4. What is a queue?
Answer
A FIFO collection — things leave in the order they arrived, like a supermarket line.
5. What is the frontier?
Answer
Also called the open set — the vertices discovered but not yet expanded. In BFS it is exactly the contents of the queue: the advancing outer edge of the wave.
6. What determines BFS’s memory use?
Answer
The size of the frontier — how wide the wave gets, not how far it travels.
7. What is a level?
Answer
Also called the layer or distance from the source — the number of edges on the shortest route from the start. Source is level 0, its neighbours level 1, and so on.
8. What is the whole reason BFS exists?
Answer
BFS assigns every vertex its correct level the first time it reaches it. The first arrival is the shortest arrival.
9. What is an unweighted graph, and why does it matter here?
Answer
One where every edge counts the same. BFS’s shortest-path guarantee holds only here, because BFS counts edges and nothing else.
10. What is a parent map?
Answer
Also the predecessor map — a dictionary recording, for each vertex, which vertex the search arrived from. It lets you recover an actual path rather than only a distance.
11. What is multi-source BFS?
Answer
BFS started from several vertices at once, by putting all of them in the queue at distance 0 before the loop begins. It computes, for every vertex, the distance to the nearest source — in one pass, at the same cost.
C. The implementation
12. State the Golden BFS Rule.
Answer
Mark a vertex visited immediately when ENQUEUING it, not when dequeuing it.
13. What goes wrong if you mark on dequeue?
Answer
Multiple neighbours enqueue duplicate copies of the same vertex before it is ever popped, blowing up memory and runtime.
14. Write the BFS skeleton.
Answer
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # on enqueue
queue.append(neighbor)15. How do you reconstruct the shortest path at the end?
Answer
Record parent[neighbor] = current as you enqueue. On reaching the target, walk backwards through parent to the source and reverse the list.
16. What does parent[start] hold, and why?
Answer
None — it is the sentinel that stops the backwards walk.
17. How do you make BFS report distances instead of paths?
Answer
Keep a dist dict: dist[neighbor] = dist[current] + 1 at enqueue time. Because the first arrival is the shortest, that value is never revised.
D. Costs
18. Time complexity, and why?
Answer
— every vertex is enqueued once and every edge examined once.
19. Space complexity, and what drives it?
Answer
— the visited set plus the queue. On wide graphs the queue alone can hold vertices.
20. On which shape of graph is BFS memory-cheaper than DFS, and on which is it worse?
Answer
BFS is cheaper on a long thin graph (frontier of one) and much worse on a wide shallow one (frontier of ). DFS is the reverse — their worst cases are opposite shapes.
E. Traps
21. Why must you never write queue.pop(0) on a Python list?
Answer
It is — every remaining element shifts down. That turns BFS into . Use collections.deque.popleft(), which is .
22. Why is BFS wrong on a weighted graph?
Answer
BFS counts edges, not cost. A path with 2 heavy edges can cost more than one with 3 light ones, so the fewest-edges answer is not the cheapest. Use Dijkstra.
23. Is there a weighted case where BFS is still correct?
Answer
Yes — when all edges have equal weight, since fewest edges then means cheapest. (And 0/1 weights have their own variant, 0-1 BFS with a deque.)
F. Choosing between BFS and DFS
24. When do you want BFS?
Answer
When the answer depends on distance from the source — shortest path in an unweighted graph, nearest match, level-by-level output, flood fill from multiple sources.
25. When do you want DFS?
Answer
When the answer depends on a whole path or on subtree results — cycle detection, topological sort, backtracking search, connected components (either works, but DFS is lighter here).
26. Both are . So what actually decides?
Answer
The guarantee you need (first-found = shortest, or not) and the memory shape of your graph (frontier width versus path depth).
27. Summarise BFS in one sentence.
Answer
Expand in rings using a queue, mark on enqueue, and the first time you touch a vertex you have already found its shortest unweighted distance.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Breadth-First Search — the module
- Depth-First Search — Question Bank — the counterpart
- Dijkstra — what to use when edges carry weights
Software engineering
Infrastructure & security
Computer science
Hardware & engineering