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.
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 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 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
def orangesRotting(grid): # LeetCode 994
ROWS, COLS = len(grid), len(grid[0])
q, fresh = deque(), 0
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
q.append((r, c)) # every rotten orange starts at once
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)): # one minute = one ring
r, c = q.popleft()
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
def canFinish(numCourses, prerequisites): # LeetCode 207
adj = defaultdict(list)
for crs, pre in prerequisites:
adj[pre].append(crs) # directed: pre -> crs
path, done = set(), set()
def dfs(c):
if c in path:
return False # back on our own route: cycle
if c in done:
return True
path.add(c)
for nxt in adj[c]:
if not dfs(nxt):
return False
path.remove(c)
done.add(c)
return True
return all(dfs(c) for c in range(numCourses))
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.
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".
| Operation | Time | Space | Why |
|---|---|---|---|
| Grid DFS or BFS | O(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 traversal | O(V + E) | O(V) extra | Each 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 storage | O(1) edge check | O(V²) | A V × V table of 0/1. Fast to ask "is there an edge?", wasteful when most pairs are not connected. |
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.
Flood out from a cell or vertex, marking visited ones.
A queue, one ring per step.
The input is a list of pairs: build adj first, then traverse.
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