考題：島嶼數量 Problem: number of islands · 演算法 Algorithms

考題：島嶼數量

數地圖上有幾塊相連的陸地：BFS（廣度優先搜尋）、DFS（深度優先搜尋）、並查集都能解，差在額外記憶體，以及陸地一格一格加進來時能不能接著算。

解法

陸地比例45%

題目

一張由 1（陸地）和 0（海）組成的格子地圖，數有幾座島：上下左右相連的陸地算同一座。例如 [[1,1,0],[0,1,0],[1,0,1]] → 3。

1/90

佇列（前端在最前）

一列一列掃描地圖。點任何一格可以切換陸地／海。

同一份輸入，所有解法
解法	答案	看過的格子＋指標步數	額外記憶體	Big O
BFS（佇列）	15 座	252	最多 2 格在等	O(R × C)
DFS（堆疊）	15 座	252	最多 3 格在等	O(R × C)
並查集	15 座	191	96 格 parent	O(R × C)

亮起來的是這一步執行的程式碼

1const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
2 
3function islandsBfs(grid: number[][]): number {
4  const h = grid.length, w = grid[0].length;
5  const seen = grid.map((row) => row.map(() => false));
6  let islands = 0;
7  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
8    if (grid[r][c] !== 1 || seen[r][c]) continue;
9    islands++;
10    seen[r][c] = true;
11    const queue = [[r, c]];
12    while (queue.length) {
13      const [cr, cc] = queue.shift()!;
14      for (const [dr, dc] of DIRS) {
15        const nr = cr + dr, nc = cc + dc;
16        if (nr >= 0 && nc >= 0 && nr < h && nc < w && grid[nr][nc] === 1 && !seen[nr][nc]) {
17          seen[nr][nc] = true;
18          queue.push([nr, nc]);
19        }
20      }
21    }
22  }
23  return islands;
24}
25 
26// Same walk with a stack: no recursion, so no stack overflow on big islands.
27function islandsDfs(grid: number[][]): number {
28  const h = grid.length, w = grid[0].length;
29  const seen = grid.map((row) => row.map(() => false));
30  let islands = 0;
31  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
32    if (grid[r][c] !== 1 || seen[r][c]) continue;
33    islands++;
34    seen[r][c] = true;
35    const stack = [[r, c]];
36    while (stack.length) {
37      const [cr, cc] = stack.pop()!;
38      for (const [dr, dc] of DIRS) {
39        const nr = cr + dr, nc = cc + dc;
40        if (nr >= 0 && nc >= 0 && nr < h && nc < w && grid[nr][nc] === 1 && !seen[nr][nc]) {
41          seen[nr][nc] = true;
42          stack.push([nr, nc]);
43        }
44      }
45    }
46  }
47  return islands;
48}
49 
50class UnionFind {
51  parent: number[];
52  size: number[];
53  constructor(n: number) {
54    this.parent = Array.from({ length: n }, (_, i) => i);
55    this.size = new Array(n).fill(1);
56  }
57  find(x: number): number {
58    while (this.parent[x] !== x) {
59      this.parent[x] = this.parent[this.parent[x]];
60      x = this.parent[x];
61    }
62    return x;
63  }
64  union(a: number, b: number): boolean {
65    let ra = this.find(a), rb = this.find(b);
66    if (ra === rb) return false;
67    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
68    this.parent[rb] = ra;
69    this.size[ra] += this.size[rb];
70    return true;
71  }
72}
73 
74function islandsUnionFind(grid: number[][]): number {
75  const h = grid.length, w = grid[0].length;
76  const uf = new UnionFind(h * w);
77  let islands = 0;
78  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
79    if (grid[r][c] !== 1) continue;
80    islands++;
81    // Only the neighbours already seen: up and left.
82    if (r > 0 && grid[r - 1][c] === 1 && uf.union(r * w + c, (r - 1) * w + c)) islands--;
83    if (c > 0 && grid[r][c - 1] === 1 && uf.union(r * w + c, r * w + c - 1)) islands--;
84  }
85  return islands;
86}
87 
88// Land arrives one cell at a time; the count is kept up to date.
89class IslandCounter {
90  uf: UnionFind;
91  land: boolean[];
92  islands = 0;
93  constructor(private h: number, private w: number) {
94    this.uf = new UnionFind(h * w);
95    this.land = new Array(h * w).fill(false);
96  }
97  addLand(r: number, c: number): number {
98    const i = r * this.w + c;
99    if (this.land[i]) return this.islands;
100    this.land[i] = true;
101    this.islands++;
102    for (const [dr, dc] of DIRS) {
103      const nr = r + dr, nc = c + dc;
104      if (nr < 0 || nc < 0 || nr >= this.h || nc >= this.w) continue;
105      if (this.land[nr * this.w + nc] && this.uf.union(i, nr * this.w + nc)) this.islands--;
106    }
107    return this.islands;
108  }
109}

追問：陸地一格一格加進來

已加入

0 / 53

島的數量

並查集累計工作

每次都用 BFS 重數

每加一格陸地，島可能變多或合併。並查集只看新格子的四個鄰居就能更新數量；BFS 或 DFS 則得把整張地圖重掃一遍。

亮起來的是這一步執行的程式碼

1const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
2 
3function islandsBfs(grid: number[][]): number {
4  const h = grid.length, w = grid[0].length;
5  const seen = grid.map((row) => row.map(() => false));
6  let islands = 0;
7  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
8    if (grid[r][c] !== 1 || seen[r][c]) continue;
9    islands++;
10    seen[r][c] = true;
11    const queue = [[r, c]];
12    while (queue.length) {
13      const [cr, cc] = queue.shift()!;
14      for (const [dr, dc] of DIRS) {
15        const nr = cr + dr, nc = cc + dc;
16        if (nr >= 0 && nc >= 0 && nr < h && nc < w && grid[nr][nc] === 1 && !seen[nr][nc]) {
17          seen[nr][nc] = true;
18          queue.push([nr, nc]);
19        }
20      }
21    }
22  }
23  return islands;
24}
25 
26// Same walk with a stack: no recursion, so no stack overflow on big islands.
27function islandsDfs(grid: number[][]): number {
28  const h = grid.length, w = grid[0].length;
29  const seen = grid.map((row) => row.map(() => false));
30  let islands = 0;
31  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
32    if (grid[r][c] !== 1 || seen[r][c]) continue;
33    islands++;
34    seen[r][c] = true;
35    const stack = [[r, c]];
36    while (stack.length) {
37      const [cr, cc] = stack.pop()!;
38      for (const [dr, dc] of DIRS) {
39        const nr = cr + dr, nc = cc + dc;
40        if (nr >= 0 && nc >= 0 && nr < h && nc < w && grid[nr][nc] === 1 && !seen[nr][nc]) {
41          seen[nr][nc] = true;
42          stack.push([nr, nc]);
43        }
44      }
45    }
46  }
47  return islands;
48}
49 
50class UnionFind {
51  parent: number[];
52  size: number[];
53  constructor(n: number) {
54    this.parent = Array.from({ length: n }, (_, i) => i);
55    this.size = new Array(n).fill(1);
56  }
57  find(x: number): number {
58    while (this.parent[x] !== x) {
59      this.parent[x] = this.parent[this.parent[x]];
60      x = this.parent[x];
61    }
62    return x;
63  }
64  union(a: number, b: number): boolean {
65    let ra = this.find(a), rb = this.find(b);
66    if (ra === rb) return false;
67    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
68    this.parent[rb] = ra;
69    this.size[ra] += this.size[rb];
70    return true;
71  }
72}
73 
74function islandsUnionFind(grid: number[][]): number {
75  const h = grid.length, w = grid[0].length;
76  const uf = new UnionFind(h * w);
77  let islands = 0;
78  for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) {
79    if (grid[r][c] !== 1) continue;
80    islands++;
81    // Only the neighbours already seen: up and left.
82    if (r > 0 && grid[r - 1][c] === 1 && uf.union(r * w + c, (r - 1) * w + c)) islands--;
83    if (c > 0 && grid[r][c - 1] === 1 && uf.union(r * w + c, r * w + c - 1)) islands--;
84  }
85  return islands;
86}
87 
88// Land arrives one cell at a time; the count is kept up to date.
89class IslandCounter {
90  uf: UnionFind;
91  land: boolean[];
92  islands = 0;
93  constructor(private h: number, private w: number) {
94    this.uf = new UnionFind(h * w);
95    this.land = new Array(h * w).fill(false);
96  }
97  addLand(r: number, c: number): number {
98    const i = r * this.w + c;
99    if (this.land[i]) return this.islands;
100    this.land[i] = true;
101    this.islands++;
102    for (const [dr, dc] of DIRS) {
103      const nr = r + dr, nc = c + dc;
104      if (nr < 0 || nc < 0 || nr >= this.h || nc >= this.w) continue;
105      if (this.land[nr * this.w + nc] && this.uf.union(i, nr * this.w + nc)) this.islands--;
106    }
107    return this.islands;
108  }
109}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

面試官要看你能不能把格子看成圖：每格是節點、上下左右是邊，數島就是數連通分量。BFS 或 DFS 都是標準答案。
被追問「陸地一格一格加進來」時換並查集：每次更新只看四個鄰居，不必整張重掃。

和其他主題的關係

由這些組成: BFS 與 DFS 資料結構 · 並查集

時間與空間複雜度（Big O）

操作	平均	最差
BFS（佇列）佇列最多約 min(R, C) 到 R×C 格	O(R × C)	O(R × C)
DFS（堆疊）遞迴寫法的呼叫深度最差是 R×C	O(R × C)	O(R × C)
並查集 α 是反阿克曼函數，實務上 ≤ 4	O(R × C · α)	O(R × C · α)
逐格加入（並查集）重數一次是 O(R × C)	O(α)	O(α)

空間：O(R × C)，標記走過的格子或 parent 陣列

Big O 實測：n 變大時步數怎麼長

數的是：看過的格子＋指標步數（n 是格子數，45% 是陸地）

	Big O	n = 1,024	n = 4,096	n = 16,384	成長倍數：實測（理論）
BFS（佇列）	O(n)	2,865	11,363	45,288	×16 (×16)
DFS（堆疊）	O(n)	2,865	11,363	45,288	×16 (×16)
並查集	O(n)	2,313	9,043	35,949	×16 (×16)

和其他做法比

	數字
逐格加入 450 格：並查集總工作	2,140
同上：每次都用 BFS 重數	799,530
全是陸地的 60×60：BFS 佇列最長	60
同上：DFS 堆疊最長	1,771
同上：遞迴寫法的 DFS 呼叫深度	3,600

30×30 的地圖逐格加入陸地時，並查集只看新格子的鄰居，總共 2,140 步；每次重新 BFS 要 799,530 步。遞迴寫的 DFS 在 3,600 格全是陸地的地圖上會深到 3,600 層，超過 Python 預設的 1,000 層上限。

真實世界裡的它

LeetCode 200（島嶼數量）、305（逐格加入的版本）、695（最大島嶼面積）、130（被包圍的區域）。
實務：影像處理的連通區域標記（connected-component labeling）、地圖上的區塊分群。

取捨與陷阱

放進佇列時就要標記，不是取出時才標：否則同一格會被加好幾次。
遞迴寫的 DFS 在大島上會超過呼叫深度上限（Python 預設 1,000）：用明確的堆疊，或改用 BFS。
直接把 grid 改成 0 當作「走過」很省記憶體，但會改到呼叫者的資料，面試時要說明。

演算法