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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Traversal