# Breadth-First and Depth-First Search — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/g-search

> Traverse graphs with BFS and DFS and apply them to real problems.

## 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.

```python
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.

**Quiz:** Why does BFS find the shortest path in an unweighted graph?

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

*Answer:* It explores nodes in order of their distance (number of edges) from the start. Level-by-level exploration reaches each node first by a shortest route.