Traversals — and "hidden graphs"
📖 Walk me through it — plain English
A graph is just a bunch of items (nodes) with connections between some of them (edges). "Traversal" means: starting from one node, visit every node you can reach by walking along edges, without ever visiting the same one twice. The whole trick of this lesson is realizing that many problems are secretly graphs. In Number of Islands the grid of "1"s and "0"s is the hidden graph: each land cell ("1") is a node, and two land cells are connected by an edge if they sit directly next to each other (up, down, left, or right). An "island" is one connected clump of land. We just count the clumps.
Analogy: imagine spilling ink on graph paper where some squares are land. You drop your finger on one piece of land and let the ink "flood" outward to every touching land square, stopping at water and at the paper's edge. That one flood paints exactly one island. Then you scan for any land you haven't inked yet, flood again, and add one to your tally. BFS (breadth-first) floods in rings outward using a queue (a line where you serve the oldest item first); DFS (depth-first) plunges as deep as it can down one path before backing up. Either one paints the same island — they just visit cells in a different order. Both versions mark cells as visited so the ink never floods backward over itself.
Let's flood this tiny 2-row, 3-column grid. Read it as land = 1 and water = 0. Top row is 1 1 0, bottom row is 0 1 0. We scan top-left to bottom-right; the moment we touch an un-inked land cell we start a flood and bump the count.
Why it works: marking each cell visited the instant you reach it guarantees no cell is ever processed twice, so one flood touches exactly the cells reachable from its starting point — that's precisely one connected island. The outer double loop guarantees you eventually start a flood from every island, and you only bump the count once per island (at its first cell). Why the cost is O(R × C) (R rows times C columns, i.e. the number of cells): every cell is looked at a constant number of times — once by the scan and at most a few times as a neighbor — and visited cells are skipped immediately, so the work grows in step with the grid's size and no faster.
Many problems are graphs in disguise: grid regions, word ladders, dependency lists. Always ask: what are the nodes? what are the edges?
from collections import deque
def num_islands(g):
R, C = len(g), len(g[0])
seen = [[False]*C for _ in range(R)]
count = 0
def bfs(r, c):
q = deque([(r, c)]); seen[r][c] = True
while q:
x, y = q.popleft()
for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx, ny = x+dx, y+dy
if 0<=nx<R and 0<=ny<C and not seen[nx][ny] and g[nx][ny]=="1":
seen[nx][ny] = True
q.append((nx, ny))
for r in range(R):
for c in range(C):
if g[r][c]=="1" and not seen[r][c]:
bfs(r, c); count += 1
return countfunction numIslands(g: string[][]): number {
const R=g.length, C=g[0].length;
let count = 0;
const dfs = (r:number, c:number) => {
if (r<0||c<0||r>=R||c>=C||g[r][c]!=="1") return;
g[r][c] = "0";
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
};
for (let r=0;r<R;r++) for (let c=0;c<C;c++)
if (g[r][c]==="1") { dfs(r,c); count++; }
return count;
}Count islands with DFS or BFS flood-fill — run it live: