Graph patterns

Graph questions often hide: a grid of cells, a list of course prerequisites, a list of friendships. Spot the vertices and edges, and the standard searches do the rest. (The Algorithms course covers them in depth, in C.)

Grids are graphs

Each cell is a vertex, joined to its 4 neighbours (up, down, left, right). Count the islands: groups of '1' cells joined side by side.

Scan the grid. At each land cell not seen yet, count a new island and flood it: visit every land cell reachable from it, marking each one.

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                islands += 1
                stack = [(r, c)]                     # flood this island
                seen.add((r, c))
                while stack:
                    y, x = stack.pop()
                    for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
                        if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == "1" and (ny, nx) not in seen:
                            seen.add((ny, nx))
                            stack.append((ny, nx))
    return islands

grid = ["1100",
        "1001",
        "0011"]
print(count_islands(grid))

The flood here is a depth-first search written with a stack, which avoids Python's recursion limit on big grids. Every cell is visited a bounded number of times: O(rows × columns).

Shortest paths: BFS

In an unweighted graph (every edge costs 1), breadth-first search finds shortest paths: it visits everything at distance 1, then 2, then 3. Use it for the fewest moves of a knight, the shortest path out of a maze, word ladder. Store each vertex's distance when it is first reached, and never visit it twice. (With weighted edges, use Dijkstra's algorithm instead.)

Ordering tasks: topological sort

Course b requires course a first. In what order can all courses be taken, if any?

This is a directed graph, and an order exists exactly when it has no cycle. Kahn's algorithm: count each course's prerequisites (its in-degree); start with the courses that need none; each time one is taken, lower the count of the courses that need it, and start any that reach 0.

from collections import deque

def course_order(n, prerequisites):
    needs = [0] * n                       # how many prerequisites each course still has
    unlocks = [[] for _ in range(n)]
    for course, before in prerequisites:
        needs[course] += 1
        unlocks[before].append(course)
    ready = deque(c for c in range(n) if needs[c] == 0)
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for nxt in unlocks[c]:
            needs[nxt] -= 1
            if needs[nxt] == 0:
                ready.append(nxt)
    return order if len(order) == n else None

print(course_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
print(course_order(2, [(0, 1), (1, 0)]))

If some courses never reach 0, they are on a cycle (a needs b and b needs a), and no order exists: the list comes back shorter than the number of courses.

Recognising the graph

Mark lesson complete