Breadth-First and Depth-First Search

Exploring a graph

Breadth-first search (BFS) explores a graph level by level using a queue (deque): first all neighbours of the start, then their neighbours, and so on. In an unweighted graph, BFS finds the shortest path (fewest edges), so it is used for degrees of separation, minimum moves in puzzles and grid shortest paths. Depth-first search (DFS) goes as deep as possible along one path before backtracking, using recursion or an explicit stack; it is used for detecting cycles, finding connected components, topological sorting, maze generation and exploring all solutions (backtracking). Both run in O(V + E) time and need a visited set to avoid revisiting nodes and looping forever in cyclic graphs. To reconstruct a path, record each node's parent when it is discovered, then walk back from the target. Grids (mazes, game boards, images) are graphs too: each cell is a vertex and its up, down, left and right neighbours are edges, so BFS on a grid solves "minimum steps" problems and flood fill counts regions.

Shortest path in a grid with BFS and components with DFS

A queue for BFS, a parent map for the path, and an iterative DFS.

from collections import deque

def shortest_path(grid: list[str], start: tuple[int, int], goal: tuple[int, int]):
    rows, cols = len(grid), len(grid[0])
    parent = {start: None}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            path, node = [], goal
            while node is not None:            # walk back through parents
                path.append(node)
                node = parent[node]
            return path[::-1]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in parent:
                parent[(nr, nc)] = (r, c)
                queue.append((nr, nc))
    return None                                # unreachable

warehouse = [
    "..#.",
    "..#.",
    "....",
]
path = shortest_path(warehouse, (0, 0), (0, 3))
print(len(path) - 1, path)                     # 7 moves around the shelf

def connected_components(graph: dict[str, list[str]]) -> list[set[str]]:
    seen, components = set(), []
    for start in graph:
        if start in seen:
            continue
        component, stack = set(), [start]
        while stack:                           # iterative DFS
            node = stack.pop()
            if node in seen:
                continue
            seen.add(node)
            component.add(node)
            stack.extend(n for n in graph[node] if n not in seen)
        components.append(component)
    return components

friends = {"asha": ["ravi"], "ravi": ["asha"], "meera": ["kabir"], "kabir": ["meera"], "zoya": []}
print(connected_components(friends))           # [{'asha', 'ravi'}, {'meera', 'kabir'}, {'zoya'}] (set order may vary)

Ripples versus a maze runner

BFS is a ripple spreading out from a stone dropped in a pond, reaching nearer points first. DFS is a maze runner who follows one corridor to its end before backtracking to try the next.

त्वरित जाँच: Why does BFS find the shortest path in an unweighted graph?

• It visits nodes randomly
• It explores nodes in order of their distance (number of edges) from the start
• It uses recursion
• It sorts the edges first