Depth-First Search (DFS) and Connected Pieces

Go deep, then backtrack

Depth-first search follows one path as far as it can, then backs up and tries the next unexplored branch. It's naturally recursive (or uses a stack).

Think of it like this: Exploring a maze with one rule: keep going until you hit a dead end, then walk back to the last junction and try a different way.

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

visited = set()
order = []

def dfs(node):
    visited.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(nxt)

dfs("A")
print(order)

Output

['A', 'B', 'D', 'E', 'F', 'C']

Counting separate groups

A connected component is a group of vertices that can all reach each other. Start a search from every vertex that hasn't been visited yet; each new start is a new group:

n = 7
edges = [(0, 1), (1, 2), (3, 4), (5, 5)]
graph = [[] for _ in range(n)]
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)

seen = [False] * n
groups = 0
for start in range(n):
    if not seen[start]:
        groups += 1
        stack = [start]                 # DFS with our own stack
        seen[start] = True
        while stack:
            node = stack.pop()
            for nxt in graph[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    stack.append(nxt)
print("groups:", groups)

Output

groups: 4

Grids are graphs too

In a grid, each cell is a vertex and its up/down/left/right neighbours are its edges. Counting islands of # on a map is counting connected components:

grid = ["##..#",
        "#...#",
        "..#..",
        "....."]
rows, cols = len(grid), len(grid[0])
seen = set()

def sink(r, c):
    if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "#" or (r, c) in seen:
        return
    seen.add((r, c))
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        sink(r + dr, c + dc)

islands = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "#" and (r, c) not in seen:
            islands += 1
            sink(r, c)
print("islands:", islands)

Output

islands: 3