Depth-first search and flood fill

BFS spreads out in rings. Depth-first search (DFS) does the opposite: it follows one way as far as it goes, and only when it's stuck does it back up to the last vertex with a way it hasn't tried yet. Many questions don't care about the order, only about which vertices can be reached. Can I get from here to there? Which cells belong to this region? How many separate groups are there? DFS answers those, and its natural form is a recursive function:

graph = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [], 6: []}
order = []


def dfs(v, seen):
    seen.add(v)
    order.append(v)
    for w in graph[v]:
        if w not in seen:
            dfs(w, seen)


dfs(1, set())
print(order)

[1, 2, 4, 6, 3, 5]

From 1 it goes to 2, from 2 to 4, from 4 to 6, and only then backs up all the way to 1 to try 3. BFS would visit 1, 2, 3, 4, 5, 6. Both find every vertex that can be reached from the start, in O(V + E).

Python's recursion limit

Each call of dfs waits on Python's call stack until the vertices below it are done, so the recursion goes as deep as the longest path the search follows. Python stops at about 1000 waiting calls:

def dfs(graph, v, seen):
    seen.add(v)
    for w in graph[v]:
        if w not in seen:
            dfs(graph, w, seen)


chain = {v: [v + 1] for v in range(5000)}
chain[5000] = []
seen = set()
dfs(chain, 0, seen)
print(len(seen))

Traceback (most recent call last):
  File "main.py", line 11, in <module>
    dfs(chain, 0, seen)
    ~~~^^^^^^^^^^^^^^^^
  File "main.py", line 5, in dfs
    dfs(graph, w, seen)
    ~~~^^^^^^^^^^^^^^^^
  File "main.py", line 5, in dfs
    dfs(graph, w, seen)
    ~~~^^^^^^^^^^^^^^^^
  File "main.py", line 5, in dfs
    dfs(graph, w, seen)
    ~~~^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

A big image, a maze with long corridors or a long chain of friends easily goes deeper than that. Raising the limit with sys.setrecursionlimit is a risky fix: the recursion goes deeper, but every waiting call still takes memory, and the browser's Python, with its smaller stack, can crash outright. Interviewers like to ask about this. The answer is to keep the waiting work in a list of your own, a stack, as in the module on trees: append pushes an item (O(1) amortized) and pop takes the one pushed last (O(1)). A list can hold millions of items.

Flood fill with a stack

A paint bucket fills the region of same-colored pixels around the one you click. That's a search on the grid, where the neighbors of a cell are the cells above, below, left and right of it with the old color. Strings can't be changed, so the picture is a list of lists of characters:

def fill(picture, row, col, color):
    old = picture[row][col]
    if old == color:
        return
    rows, cols = len(picture), len(picture[0])
    picture[row][col] = color
    stack = [(row, col)]
    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 picture[nr][nc] == old:
                picture[nr][nc] = color
                stack.append((nr, nc))


picture = [list(line) for line in ["..##..", ".#..#.", "##..#.", "..##.."]]
fill(picture, 1, 2, "o")
fill(picture, 0, 0, "~")
for line in picture:
    print("".join(line))

~~##..
~#oo#.
##oo#.
..##..

The new color marks the cells that are done, so the picture is its own visited set. A cell is painted when it's pushed, so it's never pushed twice. The stack takes the cells in another order than the recursion would, but it reaches the same cells, and that's all a fill needs. Mind the first if: when the old color is already the new color, painted cells still look unpainted, and the loop would never end.

Counting groups

The pieces of a graph that are connected inside but not to each other are its connected components: circles of friends, islands on a map, separate computer networks. To find them all, try every vertex as a start. A vertex that has been seen belongs to a group found before. Any other vertex starts a new group, and a search from it collects the whole group:

def groups(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    seen = [False] * n
    result = []
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        stack = [start]
        group = []
        while stack:
            v = stack.pop()
            group.append(v)
            for w in graph[v]:
                if not seen[w]:
                    seen[w] = True
                    stack.append(w)
        result.append(sorted(group))
    return result


print(groups(8, [(0, 3), (5, 1), (3, 6), (2, 7), (6, 0)]))

[[0, 3, 6], [1, 5], [2, 7], [4]]

The key is that seen is shared by all the searches. Each vertex is pushed and popped once in the whole run, and each edge is looked at twice: O(V + E) in all. Searching from every vertex with a fresh seen each time finds each group again from every one of its vertices: O(V·(V + E)), billions of steps for 100,000 people in a few big groups.

What it costs

DFS takes O(V + E) time like BFS, and O(V) memory for the visited marks and the stack: O(R·C) for both on a grid of R by C cells. Use BFS when the number of steps matters, and either one when only reaching matters. In Python, write it with your own stack whenever the input can be big.