BFS vs DFS: how to choose, Python code for graphs and grids, Number of Islands

Short answer. BFS vs DFS comes down to one question. Do you need the shortest path? BFS walks the graph level by level with a queue. It finds the fewest edges. DFS dives deep with a stack or recursion. It finds components, cycles and orderings. Both cost O(V + E).

What is a graph traversal?

A graph is nodes and edges. A traversal starts at one node and visits everything reachable. It visits each node once, so it needs a visited set.

BFS and DFS differ in order. BFS takes all neighbours first, then neighbours of neighbours. DFS takes one neighbour as far as it goes, then comes back.

The graph may come as an adjacency list, a matrix or a grid. The traversal code is the same. Only the way you list neighbours changes.

BFS vs DFS: how do you choose?

Trait	BFS	DFS
Structure	Queue	Stack or recursion
Shortest path, no weights	Yes	No
Components, islands	Yes	Yes, shorter code
Cycle detection, topological order	Awkward	Yes
Memory	Width of a level	Depth of a path
Risk	Huge queue on a wide graph	Stack overflow on a deep one

The rule is short. The words "shortest" or "minimum number of steps" mean BFS. Everything else, take DFS.

When does a problem need BFS or DFS?

• "Number of islands", "connected components", "flood fill".
• "Minimum steps to the exit", "shortest path in a maze".
• "Can you get from A to B", "is there a path".
• "Cells adjacent on four sides."

A grid is a graph too. A cell is a node, its four neighbours are edges. Many matrix problems are traversal problems in disguise.

What do BFS and DFS look like on one example?

Graph: A connects to B and C. B and C connect to D. Start at A.

BFS: queue [A]. Pop A, push B and C. Pop B, push D. Pop C, D already seen. Pop D. Order A, B, C, D, distances 0, 1, 1, 2.

DFS: go A, then B, then D. D has no new neighbours, return. B is done, return to A. Go to C, D already seen. Order A, B, D, C.

How do you write BFS and DFS in Python?

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in dist:
                dist[u] = dist[v] + 1
                queue.append(u)
    return dist

def dfs(graph, start, visited=None):
    visited = visited if visited is not None else set()
    visited.add(start)
    for u in graph[start]:
        if u not in visited:
            dfs(graph, u, visited)
    return visited

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def sink(r, c):
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if 0 <= nr < rows and 0 <= nc < cols \
                        and grid[nr][nc] == "1" and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    stack.append((nr, nc))

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                seen.add((r, c))
                sink(r, c)
                count += 1
    return count

In num_islands the DFS uses an explicit stack. On a 1000 by 1000 grid, recursion hits Python's depth limit.

How does DFS solve Number of Islands?

A grid of zeros and ones. An island is a group of ones touching on the sides. Count the islands.

Scan every cell. An unvisited one means a new island. Traverse from it and mark the whole island. Count the traversals you started.

Each cell is visited once. Time O(rows · cols).

Why does BFS find the shortest path?

The queue processes nodes in order of distance. All nodes at distance 1, then all at distance 2. The first time you reach a node is the shortest way there.

This only holds without weights. With weights you need Dijkstra.

What mistakes break BFS and DFS?

• Marking a node visited on leaving the queue, not on entering. One node gets queued many times.
• Using list.pop(0) instead of deque. Each pop costs O(n).
• Recursive DFS on a deep graph. Python allows about a thousand frames.
• Reading a grid cell before checking the bounds.

How do you explain BFS vs DFS in an interview?

Say how the graph is given and what counts as a neighbour. Say BFS or DFS, and why. Give O(V + E): each node and each edge is looked at once.

For a grid, mention the explicit stack or queue right away. It shows you thought about input size.

Drill this pattern on the graph BFS / DFS page. The neighbouring pattern lives on the connected components page.

FAQ

How do you recover the path after BFS?

Keep a parent dictionary. When you queue a node, record where you came from. From the target, follow parent back to the start.

What is multi-source BFS?

You queue several start nodes at distance 0. That solves "distance to the nearest zero" in one pass.

When is a plain traversal the wrong tool?

When edges have weights and you need the shortest path: use Dijkstra. When the graph changes between queries: use union-find.