Graphs

No. 10 · SVG · Marble run, with loopsmatrix DFS (stack) · matrix BFS (queue) · adjacency list

Drag across the board. Click it, then use ← → to step and Space to play.

A graph is vertices joined by edges, either one-way (directed) or two-way (undirected). It is stored as a grid, an adjacency matrix, or an adjacency list. A graph is a tree's board with the rules loosened: there is no root, any gate can connect to any other, and grooves can form loops. Because of the loops, a walk can come back to where it has already been, so every graph traversal keeps a visit set. DFS goes deep with a stack (the call stack); BFS spreads out ring by ring with a queue, which is why it finds the fewest steps.

FIG. 10 · The same board as the Trees page. Each gate is a vertex (or a grid cell) and each groove an edge. On a grid, a cell's neighbours are the four cells up, down, left and right of it. Water and empty cells are hatched walls with no grooves. Red marks what the code is looking at. Ink-filled gates are visited and finished. Small black badges show the island number, or the BFS distance (in steps or minutes). Callouts name the parts in each mode.

Step 1 / 1
READY
DFS calls
Visited
Call stack
Result
Codenum_islands
def num_islands(grid):             # matrix DFS
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()
    def dfs(r, c):
        if (r < 0 or c < 0 or r == ROWS or c == COLS
                or grid[r][c] == "0" or (r, c) in visit):
            return
        visit.add((r, c))
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc)
    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1" and (r, c) not in visit:
                dfs(r, c)
                count += 1
    return count

Examples

Matrix BFS · LeetCode 994

Each minute, rotten oranges rot their fresh neighbours. How many minutes until none are fresh? "Minimum minutes" is a fewest-steps question, so BFS: queue every rotten orange at once and count rings. Answer: 4.

O(rows × cols) timeO(rows × cols) spaceeach cell is queued at most once
Adjacency list · LeetCode 207

4 courses, prerequisites [[1,0],[2,1],[3,2],[1,3]]. Build a directed adjacency list, then DFS with a path set: reaching a course that is already on the current route means a cycle (1 → 2 → 3 → 1), so it can't be done. Trigger: "dependencies", "prerequisites".

O(V + E) timeO(V + E) spaceevery course and prerequisite is looked at once

Time and space

OperationTimeSpaceWhy
Grid DFS or BFSO(rows × cols)O(rows × cols)Each cell is visited once and looks at 4 neighbours. The visit set (and the stack or queue) can hold every cell.
Adjacency list traversalO(V + E)O(V) extraEach vertex is popped once; each edge is looked at once from each end.
Adjacency list storage—O(V + E)One list per vertex, one entry per edge end (2E for undirected).
Adjacency matrix storageO(1) edge checkO(V²)A V × V table of 0/1. Fast to ask "is there an edge?", wasteful when most pairs are not connected.

DFS or BFS on a graph?

Both visit everything in O(V + E). Pick DFS (a stack, often the call stack) when you just need to reach everything: count islands, check connectivity, find a cycle. Pick BFS (a queue) when the question is "fewest steps": it finishes all nodes 1 step away before any node 2 steps away, so the first time it reaches the target is the shortest route. That only holds when every edge costs the same.

Trigger words: which traversal the problem wants

DFS

  • grid
  • islands
  • connected
  • neighbors

Flood out from a cell or vertex, marking visited ones.

BFS

  • shortest path
  • minimum steps
  • fewest moves

A queue, one ring per step.

Adjacency list

  • edges
  • nodes
  • dependencies

The input is a list of pairs: build adj first, then traverse.

Template

from collections import defaultdict, deque

def build_adj(edges):
    adj = defaultdict(list)
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)           # remove this line if directed
    return adj

def num_islands(grid):             # matrix DFS
    ROWS, COLS = len(grid), len(grid[0])
    visit = set()
    def dfs(r, c):
        if (r < 0 or c < 0 or r == ROWS or c == COLS
                or grid[r][c] == "0" or (r, c) in visit):
            return
        visit.add((r, c))
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc)
    count = 0
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1" and (r, c) not in visit:
                dfs(r, c)
                count += 1
    return count

def shortest_path(adj, start, target):   # BFS, unweighted
    q, visit, steps = deque([start]), {start}, 0
    while q:
        for _ in range(len(q)):
            node = q.popleft()
            if node == target:
                return steps
            for nei in adj[node]:
                if nei not in visit:
                    visit.add(nei)
                    q.append(nei)
        steps += 1
    return -1