1. 問題背景與核心挑戰島嶼數量問題是LeetCode上經典的圖論類題目編號200也是面試中高頻出現的算法考題。題目要求給定一個由1陸地和0水組成的二維網格計算網格中島嶼的數量。島嶼被定義為被水包圍的、通過水平或垂直方向相鄰的陸地連接形成的區域。這個問題的現實意義在于它模擬了圖像處理中的連通區域分析、社交網絡中的群體劃分等場景。例如在衛星圖像分析中識別島嶼數量相當于檢測圖像中的獨立物體在社交網絡中則類似于發現相互關聯的用戶群體。2. 算法選型與核心思路2.1 深度優先搜索DFS解法DFS是解決島嶼問題的直觀選擇。其核心思路是當遇到一個1時以此為起點向四個方向上、下、左、右遞歸搜索相鄰的1并將訪問過的1標記為0避免重復計數。def numIslands(grid): if not grid: return 0 count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: dfs(grid, i, j) count 1 return count def dfs(grid, i, j): if i0 or j0 or ilen(grid) or jlen(grid[0]) or grid[i][j] ! 1: return grid[i][j] 0 dfs(grid, i1, j) dfs(grid, i-1, j) dfs(grid, i, j1) dfs(grid, i, j-1)2.2 廣度優先搜索BFS解法BFS使用隊列來實現同樣從發現的第一個1開始但采用層級擴展的方式探索相鄰節點from collections import deque def numIslands(grid): if not grid: return 0 count 0 queue deque() for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: queue.append((i,j)) grid[i][j] 0 while queue: x, y queue.popleft() for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny xdx, ydy if 0nxlen(grid) and 0nylen(grid[0]) and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) count 1 return count2.3 并查集Union-Find解法并查集特別適合處理動態連通性問題。我們將每個1視為獨立集合然后遍歷網格合并相鄰的1class UnionFind: def __init__(self, grid): m, n len(grid), len(grid[0]) self.count 0 self.parent [i for i in range(m*n)] self.rank [0]*(m*n) for i in range(m): for j in range(n): if grid[i][j] 1: self.count 1 def find(self, i): if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx self.find(x) rooty self.find(y) if rootx ! rooty: if self.rank[rootx] self.rank[rooty]: self.parent[rooty] rootx else: self.parent[rootx] rooty if self.rank[rootx] self.rank[rooty]: self.rank[rooty] 1 self.count - 1 def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) uf UnionFind(grid) for i in range(m): for j in range(n): if grid[i][j] 1: grid[i][j] 0 for x, y in [(i-1,j), (i1,j), (i,j-1), (i,j1)]: if 0xm and 0yn and grid[x][y] 1: uf.union(i*nj, x*ny) return uf.count3. 算法對比與性能分析3.1 時間復雜度比較假設網格大小為M×NDFS/BFSO(M×N)每個節點最多被訪問一次并查集O(M×N×α(M×N))其中α是反阿克曼函數可以認為是常數3.2 空間復雜度比較DFSO(M×N)遞歸棧最壞情況BFSO(min(M,N))隊列大小并查集O(M×N)存儲父節點和秩3.3 適用場景選擇小規模網格三種方法均可大規模網格BFS或并查集更優避免DFS棧溢出動態輸入并查集最適合支持動態合并4. 常見錯誤與邊界處理4.1 輸入驗證必須首先檢查grid是否為空if not grid or not grid[0]: return 04.2 訪問越界在DFS/BFS中必須檢查相鄰坐標是否有效if 0nxlen(grid) and 0nylen(grid[0]) and grid[nx][ny] 14.3 原地修改陷阱有些實現會創建visited數組但最優解應該直接修改原grid將訪問過的1標記為0。4.4 方向數組的最佳實踐使用方向數組使代碼更簡潔directions [(1,0), (-1,0), (0,1), (0,-1)] for dx, dy in directions: nx, ny xdx, ydy5. 面試技巧與進階問題5.1 面試回答策略先明確問題要求如是否考慮對角線連接提出暴力解法思路優化思路DFS/BFS/Union-Find分析時間/空間復雜度處理邊界條件5.2 常見變種問題島嶼的最大面積LeetCode 695封閉島嶼數量LeetCode 1254不同島嶼的數量LeetCode 694統計子島嶼LeetCode 19055.3 性能優化技巧對于特別大的網格使用迭代DFS替代遞歸DFS采用BFS的層級遍歷方式考慮并行計算分割網格后合并結果6. 實際工程應用案例6.1 圖像處理中的應用在二值圖像處理中類似的算法用于計算連通區域數量去除小面積噪聲點物體分割與計數6.2 社交網絡分析每個島嶼相當于相互關注的好友群體信息傳播的獨立路徑社區發現的初始聚類6.3 游戲開發用于地圖區域劃分可通行區域計算資源生成點分布7. 不同語言實現要點7.1 C實現注意事項使用vectorvector 表示網格BFS可用queuepairint,int注意傳遞grid時使用引用避免拷貝7.2 Java實現特點使用二維數組char[][] gridBFS可用LinkedList作為隊列注意數組邊界檢查7.3 JavaScript特殊處理需要處理可能的undefined檢查隊列可以用數組模擬shift/push注意遞歸深度限制8. 測試用例設計完整的測試應該包括空網格 []全水網格 [[0,0],[0,0]]全陸網格 [[1,1],[1,1]]常規案例最小島嶼單點最大島嶼整個網格復雜形狀島嶼示例測試def test_numIslands(): assert numIslands([]) 0 assert numIslands([[0,0],[0,0]]) 0 assert numIslands([[1,1],[1,1]]) 1 assert numIslands([ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]) 39. 可視化調試技巧9.1 打印中間狀態在DFS/BFS中打印當前網格for row in grid: print( .join(row)) print(---)9.2 使用可視化工具將網格轉為圖像顯示用不同顏色標記訪問過的節點生成搜索過程動畫9.3 調試遞歸技巧打印遞歸深度和當前坐標檢查遞歸終止條件跟蹤島嶼計數變化10. 算法優化進階10.1 并行計算優化將網格分塊處理將大網格劃分為若干子網格各線程計算子網格島嶼合并邊緣相鄰的島嶼10.2 內存優化對于極大網格使用位圖表示網格按需加載網格分區優化并查集存儲結構10.3 近似算法當不需要精確結果時采樣統計概率計數分層計算11. 學習資源推薦11.1 經典教材《算法導論》圖算法章節《編程珠璣》位圖相關章節《算法》第4版Union-Find部分11.2 在線課程LeetCode探索卡片隊列 棧Coursera算法專項課程BFS/DFS專題視頻講解11.3 實踐平臺LeetCode島嶼系列題目HackerRank圖算法挑戰Codeforces相關比賽題目12. 個人解題心得在實際刷題過程中我發現以下幾點特別重要一定要先手動模擬小規模案例確保完全理解問題要求。曾經因為沒注意島嶼是四連通還是八連通而浪費大量時間。DFS實現時Python的默認遞歸深度限制可能導致棧溢出。對于100×100以上的網格建議改用BFS或迭代式DFS。并查集的路徑壓縮和按秩合并不是必須的但能顯著提升性能。在面試中如果時間有限可以先實現基礎版本。測試時要特別注意邊緣情況比如全1、全0、單行、單列等特殊網格。我曾在面試中因為沒處理空輸入而被扣分。對于變種問題如統計島嶼周長通常只需要修改核心搜索邏輯中的計數方式整體框架可以復用。 LeetCode島嶼問題：DFS、BFS與并查集算法詳解
1. 問題背景與核心挑戰島嶼數量問題是LeetCode上經典的圖論類題目編號200也是面試中高頻出現的算法考題。題目要求給定一個由1陸地和0水組成的二維網格計算網格中島嶼的數量。島嶼被定義為被水包圍的、通過水平或垂直方向相鄰的陸地連接形成的區域。這個問題的現實意義在于它模擬了圖像處理中的連通區域分析、社交網絡中的群體劃分等場景。例如在衛星圖像分析中識別島嶼數量相當于檢測圖像中的獨立物體在社交網絡中則類似于發現相互關聯的用戶群體。2. 算法選型與核心思路2.1 深度優先搜索DFS解法DFS是解決島嶼問題的直觀選擇。其核心思路是當遇到一個1時以此為起點向四個方向上、下、左、右遞歸搜索相鄰的1并將訪問過的1標記為0避免重復計數。def numIslands(grid): if not grid: return 0 count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: dfs(grid, i, j) count 1 return count def dfs(grid, i, j): if i0 or j0 or ilen(grid) or jlen(grid[0]) or grid[i][j] ! 1: return grid[i][j] 0 dfs(grid, i1, j) dfs(grid, i-1, j) dfs(grid, i, j1) dfs(grid, i, j-1)2.2 廣度優先搜索BFS解法BFS使用隊列來實現同樣從發現的第一個1開始但采用層級擴展的方式探索相鄰節點from collections import deque def numIslands(grid): if not grid: return 0 count 0 queue deque() for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: queue.append((i,j)) grid[i][j] 0 while queue: x, y queue.popleft() for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny xdx, ydy if 0nxlen(grid) and 0nylen(grid[0]) and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) count 1 return count2.3 并查集Union-Find解法并查集特別適合處理動態連通性問題。我們將每個1視為獨立集合然后遍歷網格合并相鄰的1class UnionFind: def __init__(self, grid): m, n len(grid), len(grid[0]) self.count 0 self.parent [i for i in range(m*n)] self.rank [0]*(m*n) for i in range(m): for j in range(n): if grid[i][j] 1: self.count 1 def find(self, i): if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx self.find(x) rooty self.find(y) if rootx ! rooty: if self.rank[rootx] self.rank[rooty]: self.parent[rooty] rootx else: self.parent[rootx] rooty if self.rank[rootx] self.rank[rooty]: self.rank[rooty] 1 self.count - 1 def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) uf UnionFind(grid) for i in range(m): for j in range(n): if grid[i][j] 1: grid[i][j] 0 for x, y in [(i-1,j), (i1,j), (i,j-1), (i,j1)]: if 0xm and 0yn and grid[x][y] 1: uf.union(i*nj, x*ny) return uf.count3. 算法對比與性能分析3.1 時間復雜度比較假設網格大小為M×NDFS/BFSO(M×N)每個節點最多被訪問一次并查集O(M×N×α(M×N))其中α是反阿克曼函數可以認為是常數3.2 空間復雜度比較DFSO(M×N)遞歸棧最壞情況BFSO(min(M,N))隊列大小并查集O(M×N)存儲父節點和秩3.3 適用場景選擇小規模網格三種方法均可大規模網格BFS或并查集更優避免DFS棧溢出動態輸入并查集最適合支持動態合并4. 常見錯誤與邊界處理4.1 輸入驗證必須首先檢查grid是否為空if not grid or not grid[0]: return 04.2 訪問越界在DFS/BFS中必須檢查相鄰坐標是否有效if 0nxlen(grid) and 0nylen(grid[0]) and grid[nx][ny] 14.3 原地修改陷阱有些實現會創建visited數組但最優解應該直接修改原grid將訪問過的1標記為0。4.4 方向數組的最佳實踐使用方向數組使代碼更簡潔directions [(1,0), (-1,0), (0,1), (0,-1)] for dx, dy in directions: nx, ny xdx, ydy5. 面試技巧與進階問題5.1 面試回答策略先明確問題要求如是否考慮對角線連接提出暴力解法思路優化思路DFS/BFS/Union-Find分析時間/空間復雜度處理邊界條件5.2 常見變種問題島嶼的最大面積LeetCode 695封閉島嶼數量LeetCode 1254不同島嶼的數量LeetCode 694統計子島嶼LeetCode 19055.3 性能優化技巧對于特別大的網格使用迭代DFS替代遞歸DFS采用BFS的層級遍歷方式考慮并行計算分割網格后合并結果6. 實際工程應用案例6.1 圖像處理中的應用在二值圖像處理中類似的算法用于計算連通區域數量去除小面積噪聲點物體分割與計數6.2 社交網絡分析每個島嶼相當于相互關注的好友群體信息傳播的獨立路徑社區發現的初始聚類6.3 游戲開發用于地圖區域劃分可通行區域計算資源生成點分布7. 不同語言實現要點7.1 C實現注意事項使用vectorvector 表示網格BFS可用queuepairint,int注意傳遞grid時使用引用避免拷貝7.2 Java實現特點使用二維數組char[][] gridBFS可用LinkedList作為隊列注意數組邊界檢查7.3 JavaScript特殊處理需要處理可能的undefined檢查隊列可以用數組模擬shift/push注意遞歸深度限制8. 測試用例設計完整的測試應該包括空網格 []全水網格 [[0,0],[0,0]]全陸網格 [[1,1],[1,1]]常規案例最小島嶼單點最大島嶼整個網格復雜形狀島嶼示例測試def test_numIslands(): assert numIslands([]) 0 assert numIslands([[0,0],[0,0]]) 0 assert numIslands([[1,1],[1,1]]) 1 assert numIslands([ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]) 39. 可視化調試技巧9.1 打印中間狀態在DFS/BFS中打印當前網格for row in grid: print( .join(row)) print(---)9.2 使用可視化工具將網格轉為圖像顯示用不同顏色標記訪問過的節點生成搜索過程動畫9.3 調試遞歸技巧打印遞歸深度和當前坐標檢查遞歸終止條件跟蹤島嶼計數變化10. 算法優化進階10.1 并行計算優化將網格分塊處理將大網格劃分為若干子網格各線程計算子網格島嶼合并邊緣相鄰的島嶼10.2 內存優化對于極大網格使用位圖表示網格按需加載網格分區優化并查集存儲結構10.3 近似算法當不需要精確結果時采樣統計概率計數分層計算11. 學習資源推薦11.1 經典教材《算法導論》圖算法章節《編程珠璣》位圖相關章節《算法》第4版Union-Find部分11.2 在線課程LeetCode探索卡片隊列 棧Coursera算法專項課程BFS/DFS專題視頻講解11.3 實踐平臺LeetCode島嶼系列題目HackerRank圖算法挑戰Codeforces相關比賽題目12. 個人解題心得在實際刷題過程中我發現以下幾點特別重要一定要先手動模擬小規模案例確保完全理解問題要求。曾經因為沒注意島嶼是四連通還是八連通而浪費大量時間。DFS實現時Python的默認遞歸深度限制可能導致棧溢出。對于100×100以上的網格建議改用BFS或迭代式DFS。并查集的路徑壓縮和按秩合并不是必須的但能顯著提升性能。在面試中如果時間有限可以先實現基礎版本。測試時要特別注意邊緣情況比如全1、全0、單行、單列等特殊網格。我曾在面試中因為沒處理空輸入而被扣分。對于變種問題如統計島嶼周長通常只需要修改核心搜索邏輯中的計數方式整體框架可以復用。