BFS and DFS
Swap the container and the traversal changes character: why a queue gives shortest paths, why a stack does not, and where to mark a node visited.
Breadth-first and depth-first search are the same loop with a different container. Take a node out, mark and push its unvisited neighbours, repeat. Take from the front and you get level order; take from the back and you dive. That one-line difference decides whether the traversal hands you shortest paths.
One loop, two containers
from collections import deque
def traverse(graph, start, use_queue):
seen = {start}
frontier = deque([start])
order = []
while frontier:
u = frontier.popleft() if use_queue else frontier.pop()
order.append(u)
for v in graph[u]:
if v not in seen:
seen.add(v) # mark on push, not on pop
frontier.append(v)
return order
Both cost O(V + E): every node enters the frontier once, and every adjacency entry is examined once. On an adjacency list of V = 10⁵ nodes and E = 2 × 10⁵ edges that is about 3 × 10⁵ steps — instant. Space is O(V) for the visited set plus the frontier, which in the worst case holds a whole level.
Which neighbour is explored first depends on the order neighbours sit in each adjacency list, so the two visit orders below are one pair among several. What does not vary is the shape: the queue sweeps outwards a level at a time, the stack commits to a branch and follows it down.
Why BFS gives shortest paths and DFS does not
BFS removes nodes in non-decreasing order of distance from the source. When a node is first discovered, everything still in the queue is at distance d or d + 1, so any other route to that node has to pass through a node at distance ≥ d and arrive at d + 1 or later. There is no shorter route left to find. The distance recorded on first discovery is therefore final:
def distances(graph, start):
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist
DFS has no such ordering. It follows one branch as far as it goes, so the first time it reaches a node may be down a detour of length 12 when a two-edge route existed. The node is now marked visited, and the short route never gets to claim it. In the diagram above, B is one edge from the source and DFS arrives there sixth, by way of a three-deep dive. DFS answers is there a path correctly and what is the shortest path only by accident.
This is the fact worth carrying out of the module: unweighted shortest path means BFS. Weighted is a different question, handled in shortest paths.
Mark on push, not on pop
Marking a node when you take it out of the frontier instead of when you put it in is a bug that still returns the right answer, which is why it survives. A node with k edges into it gets pushed up to k times before its first pop, so the frontier holds O(E) entries rather than O(V). On a 1,000 × 1,000 grid that is up to 4 million queue entries instead of 1 million, four times the memory for nothing.
Worse is the version with no check on the pop either. Then every duplicate is expanded again, and each re-expansion pushes its neighbours again — the work compounds instead of terminating in O(V + E). On a cyclic graph it does not terminate at all.
Mark on push and each node enters the frontier exactly once.
Components by repeated traversal
A traversal reaches one connected component. Run it from every node that is still unmarked and you have counted them:
def count_components(n, graph):
seen = [False] * n
count = 0
for s in range(n):
if seen[s]:
continue
count += 1
stack, seen[s] = [s], True
while stack:
u = stack.pop()
for v in graph[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
return count
The outer loop looks like it multiplies the cost, and it does not: each node is pushed once across all traversals and each edge is examined once, so the total is still O(V + E). The same shape counts islands in a grid, groups friends, or finds the largest region — only the neighbour function changes.
Multi-source BFS
When the question is "distance to the nearest of k sources", the naive answer runs BFS k times and takes the minimum, at O(k(V + E)). Instead seed the queue with all k sources at distance 0. The layers then expand from every source at once, and the first time a node is reached it is reached from whichever source is closest:
q = deque(sources)
dist = {s: 0 for s in sources}
Nothing else in the loop changes. With k = 1,000 sources on a 10⁶-cell grid the repeated version is about 1,000 × 3 × 10⁶ = 3 × 10⁹ steps, which at roughly 10⁸ operations per second is half a minute; the single multi-source pass is 3 × 10⁶ steps. A factor of a thousand for one edit to the initialisation.
Recursion is a stack you did not declare
Recursive DFS is the same algorithm with the call stack as the container. It is shorter to write and it fails on deep graphs: a path graph of 10⁶ nodes recurses a million frames deep, and Python's default limit is 1,000. Either raise the limit and the thread stack size, or use the explicit stack above. On an interview whiteboard say which you are doing and why.
In an interview
Name the container and the reason in the same breath: "BFS, because the edges are unweighted and I need the shortest number of moves — a queue gives me non-decreasing distance order." That sentence covers the choice and its justification, and it is most of what the question is testing.
The mistake that loses points: reaching for DFS on a shortest-path question because it is fewer lines, then patching it with "take the minimum over all paths". That patch turns O(V + E) into an exponential enumeration of every path, and it announces that the ordering property was never understood.
Check yourself
A grid with 10⁶ cells, and you mark cells visited on dequeue rather than on enqueue. What is the worst-case queue length, and does the answer change?
Each cell has up to four in-edges, so it can be enqueued up to four times before its first dequeue — up to 4 × 10⁶ entries instead of 10⁶. The distances stay correct as long as you still check the visited set after dequeuing; you have paid four times the memory and the extra pushes and pops for it.
Why can DFS report a distance of 12 for a node two edges from the source?
DFS commits to a branch. It can reach that node along a long path, mark it visited there, and never revisit it when the two-edge route is finally explored. BFS cannot, because it removes nodes in non-decreasing distance order, so the first arrival is the shortest.
You need the distance from every cell to the nearest of 500 exits. What do you run, and what does it save?
One multi-source BFS with all 500 exits seeded at distance 0. Running BFS from each exit separately costs 500 times as much for the same answer.