Unit 8: Maps and Mazes

Nodes and edges, and nothing else

Towns joined by roads. Friends who know each other. Rooms with doors between them. All the same thing: nodes and edges.

A contest gives you them as numbers — how many nodes, how many edges, then the edges one per line — and the first thing you do is turn that into a list of neighbours.

Python

n = 5
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

adj = [[] for i in range(n)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

for i in range(n):
    print(i, adj[i])

It prints

0 [1, 2]
1 [0, 3]
2 [0, 3]
3 [1, 2, 4]
4 [3]

Both ends, unless the roads are one-way

An undirected edge goes in the list twice — once at each end. A directed edge, like a one-way street or "a must happen before b", is added only one way.

Forgetting the second append on an undirected graph is the single most common graph bug there is.

Why not a grid of every pair?

A table of "is there a road from i to j" is easy to write and impossible to afford: 100000 nodes would need ten thousand million boxes.

The neighbour lists hold two entries per edge and nothing else, so a graph with 200000 roads costs 400000 entries. That is the whole reason contests use them.

Python

n = 100000
m = 200000
print(n * n)
print(2 * m)

It prints

10000000000
400000

Walk as far as you can, then back up

Mark where you are. Step to a neighbour you have not marked. Keep going until you are stuck, then back up and try the other doors.

That is depth first search, and with recursion it is five lines. The visited list is what stops it going round in circles for ever.

Python

adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
visited = [False] * 5

def dfs(node):
    visited[node] = True
    print(node)
    for nxt in adj[node]:
        if not visited[nxt]:
            dfs(nxt)

dfs(0)

It prints

0
1
3
2
4

What one search reaches is one group

A search from a node reaches exactly the nodes joined to it. So to count the separate groups in a graph, start a search from every node that has not been visited yet, and count how many times you had to start.

Seven friends, five friendships, two groups.

Python

n = 7
edges = [(0, 1), (1, 2), (3, 4), (5, 6), (6, 3)]

adj = [[] for i in range(n)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

visited = [False] * n

def dfs(node):
    visited[node] = True
    for nxt in adj[node]:
        if not visited[nxt]:
            dfs(nxt)

groups = 0
for i in range(n):
    if not visited[i]:
        groups += 1
        dfs(i)

print(groups)

It prints

2

A grid is a graph in disguise

Every square is a node; its neighbours are up, down, left and right. Nobody builds the adjacency list — you just look at the four squares.

Searching from every unvisited land square counts the islands, and the size of each search is the size of that island.

Python

grid = [
    "##..",
    "#..#",
    "..##",
]
rows = 3
cols = 4
seen = [[False] * cols for r in range(rows)]

def fill(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return 0
    if seen[r][c] or grid[r][c] == ".":
        return 0
    seen[r][c] = True
    return 1 + fill(r + 1, c) + fill(r - 1, c) + fill(r, c + 1) + fill(r, c - 1)

islands = 0
biggest = 0
for r in range(rows):
    for c in range(cols):
        size = fill(r, c)
        if size > 0:
            islands += 1
            biggest = max(biggest, size)

print(islands, biggest)

It prints

2 3

The trap nobody warns you about

Python refuses to recurse more than about a thousand deep. A contest graph of 100000 nodes in a line will crash a recursive DFS — and the error looks nothing like "your algorithm is wrong".

Two cures: raise the limit at the top of your program, or keep your own stack in a list and loop.

Python

import sys
sys.setrecursionlimit(300000)

adj = [[1], [0, 2], [1]]
stack = [0]
visited = [False] * 3
order = []
while stack:
    node = stack.pop()
    if visited[node]:
        continue
    visited[node] = True
    order.append(node)
    for nxt in adj[node]:
        if not visited[nxt]:
            stack.append(nxt)

print(order)

It prints

[0, 1, 2]

Everything one step away, then everything two steps away

Breadth first search spreads out in rings. Keep a queue: take the node at the front, put its unseen neighbours on the back.

Because the rings come out in order, the first time you reach a node is by the shortest route. That is the whole reason it exists.

Python

from collections import deque

adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
dist = [-1] * 5
dist[0] = 0
queue = deque([0])

while queue:
    node = queue.popleft()
    for nxt in adj[node]:
        if dist[nxt] == -1:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)

print(dist)

It prints

[0, 1, 1, 2, 3]

The queue is doing the work, not the code

A stack takes the newest thing and dives — that is DFS. A queue takes the oldest and spreads — that is BFS. One word changed, an entirely different search.

Use deque and popleft. Taking from the front of an ordinary list copies the whole list every time, which quietly turns a fast program into an O(n * n) one.

Remember who you came from and you have the route

Distances alone rarely satisfy a problem setter. Record, for each node, which node reached it first — then walk that chain backwards from the destination and reverse it.

-1 marks the start, which is where the walk stops.

Python

from collections import deque

adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
parent = [-2] * 5
parent[0] = -1
queue = deque([0])

while queue:
    node = queue.popleft()
    for nxt in adj[node]:
        if parent[nxt] == -2:
            parent[nxt] = node
            queue.append(nxt)

path = []
node = 4
while node != -1:
    path.append(node)
    node = parent[node]

print(path[::-1])

It prints

[0, 1, 3, 4]

Why the first arrival is always the best one

Suppose a node were reachable in 3 steps but BFS first met it in 5. The 3-step route passes through some node at distance 2 — and BFS had already finished with everything at distance 2 before it started on distance 4.

So it would have arrived earlier. The contradiction is the proof, and it needs every edge to cost the same. As soon as roads have lengths, this argument breaks and you need unit 9.

A maze is a graph you never build

Walls are #, floor is ., you start at S and want E. The neighbours of a square are the four squares beside it that are on the board and are not wall.

BFS over that, and the distance to E is the fewest steps out.

The four steps, written once

A list of the four moves keeps the code short and stops you writing the same four lines four times — which is where the copy-paste mistakes live.

Python

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
r = 2
c = 3
for dr, dc in moves:
    print(r + dr, c + dc)

It prints

3 3
1 3
2 4
2 2

The whole maze solver

Find the start, put it in the queue at distance 0, and spread. Every square you step onto must be inside the maze, not a wall, and not already reached.

Five steps out of this one, and the wall in the middle is the reason it is not four.

Python

from collections import deque

maze = [
    "S..#",
    ".#..",
    "...E",
]
rows = 3
cols = 4

dist = [[-1] * cols for r in range(rows)]
queue = deque()
for r in range(rows):
    for c in range(cols):
        if maze[r][c] == "S":
            dist[r][c] = 0
            queue.append((r, c))

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
    r, c = queue.popleft()
    for dr, dc in moves:
        nr = r + dr
        nc = c + dc
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
            continue
        if maze[nr][nc] == "#" or dist[nr][nc] != -1:
            continue
        dist[nr][nc] = dist[r][c] + 1
        queue.append((nr, nc))

for row in dist:
    print(row)

It prints

[0, 1, 2, -1]
[1, -1, 3, 4]
[2, 3, 4, 5]

Reading the map of distances

Every number is the fewest steps to that square, and -1 is a wall or a square with no way in. The exit reads 5.

A whole grid of answers for the price of one search: that is why BFS is worth reaching for even when only one number was asked about.