LeetCode Hot100（35/100）——200. 岛屿数量

文章目录

• • 一、题目简介
  • 二、问题本质
  • 三、解法总体思维导图
  • 四、方法一：深度优先搜索（DFS）
  • • 解题思路
    • DFS 过程流程图
    • Java代码实现
    • 复杂度分析
  • 五、方法二：广度优先搜索（BFS）
  • • 解题思路
    • BFS 时序图
    • Java代码实现
    • 复杂度分析
  • 六、方法三：并查集（Union-Find）
  • • 解题原理
    • 并查集流程图
    • Java代码实现
    • 复杂度分析
  • 七、总结对比

一、题目简介

题目链接： LeetCode – Number of Islands

题目描述：

给你一个 m × n 的二维网格 grid，由字符 '1'（陆地）和 '0'（水域）组成。请你计算网格中 岛屿 的数量。岛屿被水包围，可以由水平或垂直方向相邻的陆地连接形成。

示例输入：

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

示例输出：

3

解释：上图中存在三个岛屿。

二、问题本质

岛屿数量问题的核心是： 将矩阵看作一个图，"1" 表示陆地，"0" 表示水域。岛屿是一个连通分量（Connected Component）。

我们需要计算：

• 以 '1' 为节点；
• 上下左右方向为边；
• 统计这个“图”中连通分量的数量。

三、解法总体思维导图

#mermaid-svg-g8d8RQg8JgIpuDyd{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-g8d8RQg8JgIpuDyd .error-icon{fill:#552222;}#mermaid-svg-g8d8RQg8JgIpuDyd .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-g8d8RQg8JgIpuDyd .marker{fill:#333333;stroke:#333333;}#mermaid-svg-g8d8RQg8JgIpuDyd .marker.cross{stroke:#333333;}#mermaid-svg-g8d8RQg8JgIpuDyd svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-g8d8RQg8JgIpuDyd p{margin:0;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge{stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 text{fill:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth–1{stroke-width:17;}#mermaid-svg-g8d8RQg8JgIpuDyd .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-0{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-0{stroke-width:14;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-1{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-1{stroke-width:11;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 text{fill:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-2{stroke-width:8;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-3{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-3{stroke-width:5;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-4{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-4{stroke-width:2;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-5{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-5{stroke-width:-1;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-6{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-6{stroke-width:-4;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-7{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-7{stroke-width:-7;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-8{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-8{stroke-width:-10;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-9{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-9{stroke-width:-13;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 polygon,#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 text{fill:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .node-icon-10{font-size:40px;color:black;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .edge-depth-10{stroke-width:-16;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled circle,#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:lightgray;}#mermaid-svg-g8d8RQg8JgIpuDyd .disabled text{fill:#efefef;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-root rect,#mermaid-svg-g8d8RQg8JgIpuDyd .section-root path,#mermaid-svg-g8d8RQg8JgIpuDyd .section-root circle,#mermaid-svg-g8d8RQg8JgIpuDyd .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-g8d8RQg8JgIpuDyd .section-root text{fill:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-root span{color:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .section-2 span{color:#ffffff;}#mermaid-svg-g8d8RQg8JgIpuDyd .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-g8d8RQg8JgIpuDyd .edge{fill:none;}#mermaid-svg-g8d8RQg8JgIpuDyd .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-g8d8RQg8JgIpuDyd :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

岛屿数量

DFS

标记访问过的节点

递归遍历相邻陆地

时间复杂度 O(m*n)

空间复杂度 O(m*n)

BFS

使用队列保存待访问节点

层层扩展陆地

时间复杂度 O(m*n)

空间复杂度 O(min(m,n))

Union-Find

每个格子设为一个节点

通过合并操作连接陆地

最终统计父节点数量

时间复杂度 O(mnα(m*n))

空间复杂度 O(m*n)

四、方法一：深度优先搜索（DFS）

解题思路

DFS 过程流程图

#mermaid-svg-YatTEYdMyJhiULkg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-YatTEYdMyJhiULkg .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-YatTEYdMyJhiULkg .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-YatTEYdMyJhiULkg .error-icon{fill:#552222;}#mermaid-svg-YatTEYdMyJhiULkg .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-YatTEYdMyJhiULkg .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-YatTEYdMyJhiULkg .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-YatTEYdMyJhiULkg .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-YatTEYdMyJhiULkg .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-YatTEYdMyJhiULkg .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-YatTEYdMyJhiULkg .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-YatTEYdMyJhiULkg .marker{fill:#333333;stroke:#333333;}#mermaid-svg-YatTEYdMyJhiULkg .marker.cross{stroke:#333333;}#mermaid-svg-YatTEYdMyJhiULkg svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-YatTEYdMyJhiULkg p{margin:0;}#mermaid-svg-YatTEYdMyJhiULkg .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-YatTEYdMyJhiULkg .cluster-label text{fill:#333;}#mermaid-svg-YatTEYdMyJhiULkg .cluster-label span{color:#333;}#mermaid-svg-YatTEYdMyJhiULkg .cluster-label span p{background-color:transparent;}#mermaid-svg-YatTEYdMyJhiULkg .label text,#mermaid-svg-YatTEYdMyJhiULkg span{fill:#333;color:#333;}#mermaid-svg-YatTEYdMyJhiULkg .node rect,#mermaid-svg-YatTEYdMyJhiULkg .node circle,#mermaid-svg-YatTEYdMyJhiULkg .node ellipse,#mermaid-svg-YatTEYdMyJhiULkg .node polygon,#mermaid-svg-YatTEYdMyJhiULkg .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-YatTEYdMyJhiULkg .rough-node .label text,#mermaid-svg-YatTEYdMyJhiULkg .node .label text,#mermaid-svg-YatTEYdMyJhiULkg .image-shape .label,#mermaid-svg-YatTEYdMyJhiULkg .icon-shape .label{text-anchor:middle;}#mermaid-svg-YatTEYdMyJhiULkg .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-YatTEYdMyJhiULkg .rough-node .label,#mermaid-svg-YatTEYdMyJhiULkg .node .label,#mermaid-svg-YatTEYdMyJhiULkg .image-shape .label,#mermaid-svg-YatTEYdMyJhiULkg .icon-shape .label{text-align:center;}#mermaid-svg-YatTEYdMyJhiULkg .node.clickable{cursor:pointer;}#mermaid-svg-YatTEYdMyJhiULkg .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-YatTEYdMyJhiULkg .arrowheadPath{fill:#333333;}#mermaid-svg-YatTEYdMyJhiULkg .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-YatTEYdMyJhiULkg .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-YatTEYdMyJhiULkg .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-YatTEYdMyJhiULkg .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-YatTEYdMyJhiULkg .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-YatTEYdMyJhiULkg .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-YatTEYdMyJhiULkg .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-YatTEYdMyJhiULkg .cluster text{fill:#333;}#mermaid-svg-YatTEYdMyJhiULkg .cluster span{color:#333;}#mermaid-svg-YatTEYdMyJhiULkg div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-YatTEYdMyJhiULkg .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-YatTEYdMyJhiULkg rect.text{fill:none;stroke-width:0;}#mermaid-svg-YatTEYdMyJhiULkg .icon-shape,#mermaid-svg-YatTEYdMyJhiULkg .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-YatTEYdMyJhiULkg .icon-shape p,#mermaid-svg-YatTEYdMyJhiULkg .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-YatTEYdMyJhiULkg .icon-shape rect,#mermaid-svg-YatTEYdMyJhiULkg .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-YatTEYdMyJhiULkg .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-YatTEYdMyJhiULkg .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-YatTEYdMyJhiULkg :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

开始遍历grid

当前格子是1吗?

岛屿数量+1

调用DFS递归标记相邻陆地

继续遍历下一个格子

遍历结束返回计数

Java代码实现

class Solution {
public int numIslands(char[][] grid) {
int count = 0;
int rows = grid.length;
if (rows == 0) return 0;
int cols = grid[0].length;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}

private void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // 标记访问过
dfs(grid, i + 1, j);
dfs(grid, i – 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j – 1);
}
}

复杂度分析

五、方法二：广度优先搜索（BFS）

解题思路

• 与 DFS 类似，只是使用队列代替栈；
• 每当发现新的陆地，将其入队；
• 不断扩展相邻节点，完成一整个岛屿的遍历。

BFS 时序图

Algorithm

Queue

Grid

Algorithm

Queue

Grid

#mermaid-svg-9Cqkc6uyFbWbcGpP{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-9Cqkc6uyFbWbcGpP .error-icon{fill:#552222;}#mermaid-svg-9Cqkc6uyFbWbcGpP .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-9Cqkc6uyFbWbcGpP .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-9Cqkc6uyFbWbcGpP .marker{fill:#333333;stroke:#333333;}#mermaid-svg-9Cqkc6uyFbWbcGpP .marker.cross{stroke:#333333;}#mermaid-svg-9Cqkc6uyFbWbcGpP svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-9Cqkc6uyFbWbcGpP p{margin:0;}#mermaid-svg-9Cqkc6uyFbWbcGpP .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-9Cqkc6uyFbWbcGpP text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .actor-line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-9Cqkc6uyFbWbcGpP .innerArc{stroke-width:1.5;stroke-dasharray:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-9Cqkc6uyFbWbcGpP .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-9Cqkc6uyFbWbcGpP #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-9Cqkc6uyFbWbcGpP .sequenceNumber{fill:white;}#mermaid-svg-9Cqkc6uyFbWbcGpP #sequencenumber{fill:#333;}#mermaid-svg-9Cqkc6uyFbWbcGpP #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-9Cqkc6uyFbWbcGpP .messageText{fill:#333;stroke:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-9Cqkc6uyFbWbcGpP .labelText,#mermaid-svg-9Cqkc6uyFbWbcGpP .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .loopText,#mermaid-svg-9Cqkc6uyFbWbcGpP .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-9Cqkc6uyFbWbcGpP .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-9Cqkc6uyFbWbcGpP .noteText,#mermaid-svg-9Cqkc6uyFbWbcGpP .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-9Cqkc6uyFbWbcGpP .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-9Cqkc6uyFbWbcGpP .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-9Cqkc6uyFbWbcGpP .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-9Cqkc6uyFbWbcGpP .actorPopupMenu{position:absolute;}#mermaid-svg-9Cqkc6uyFbWbcGpP .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-9Cqkc6uyFbWbcGpP .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-9Cqkc6uyFbWbcGpP .actor-man circle,#mermaid-svg-9Cqkc6uyFbWbcGpP line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-9Cqkc6uyFbWbcGpP :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

loop

[每个队列元素]

遍历发现‘1’

加入队列

取出当前节点

标记为‘0’

加入相邻陆地

完成一个岛屿扩展

Java代码实现

import java.util.*;

class Solution {
public int numIslands(char[][] grid) {
int count = 0;
int rows = grid.length;
if (rows == 0) return 0;
int cols = grid[0].length;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
bfs(grid, i, j);
}
}
}
return count;
}

private void bfs(char[][] grid, int x, int y) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
grid[x][y] = '0';

int[][] dirs = {{1,0},{–1,0},{0,1},{0,–1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : dirs) {
int nx = cur[0] + d[0];
int ny = cur[1] + d[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
queue.offer(new int[]{nx, ny});
}
}
}
}
}

复杂度分析

六、方法三：并查集（Union-Find）

解题原理

• 将每个陆地格子看作一个节点；
• 若相邻两格都是 '1'，则进行 “合并” 操作；
• 最后统计有多少个不同的集合（根节点数量），即岛屿数量。

并查集流程图

#mermaid-svg-f7UyXpk7mNanGJfK{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-f7UyXpk7mNanGJfK .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-f7UyXpk7mNanGJfK .error-icon{fill:#552222;}#mermaid-svg-f7UyXpk7mNanGJfK .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-f7UyXpk7mNanGJfK .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-f7UyXpk7mNanGJfK .marker{fill:#333333;stroke:#333333;}#mermaid-svg-f7UyXpk7mNanGJfK .marker.cross{stroke:#333333;}#mermaid-svg-f7UyXpk7mNanGJfK svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-f7UyXpk7mNanGJfK p{margin:0;}#mermaid-svg-f7UyXpk7mNanGJfK .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-f7UyXpk7mNanGJfK .cluster-label text{fill:#333;}#mermaid-svg-f7UyXpk7mNanGJfK .cluster-label span{color:#333;}#mermaid-svg-f7UyXpk7mNanGJfK .cluster-label span p{background-color:transparent;}#mermaid-svg-f7UyXpk7mNanGJfK .label text,#mermaid-svg-f7UyXpk7mNanGJfK span{fill:#333;color:#333;}#mermaid-svg-f7UyXpk7mNanGJfK .node rect,#mermaid-svg-f7UyXpk7mNanGJfK .node circle,#mermaid-svg-f7UyXpk7mNanGJfK .node ellipse,#mermaid-svg-f7UyXpk7mNanGJfK .node polygon,#mermaid-svg-f7UyXpk7mNanGJfK .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-f7UyXpk7mNanGJfK .rough-node .label text,#mermaid-svg-f7UyXpk7mNanGJfK .node .label text,#mermaid-svg-f7UyXpk7mNanGJfK .image-shape .label,#mermaid-svg-f7UyXpk7mNanGJfK .icon-shape .label{text-anchor:middle;}#mermaid-svg-f7UyXpk7mNanGJfK .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-f7UyXpk7mNanGJfK .rough-node .label,#mermaid-svg-f7UyXpk7mNanGJfK .node .label,#mermaid-svg-f7UyXpk7mNanGJfK .image-shape .label,#mermaid-svg-f7UyXpk7mNanGJfK .icon-shape .label{text-align:center;}#mermaid-svg-f7UyXpk7mNanGJfK .node.clickable{cursor:pointer;}#mermaid-svg-f7UyXpk7mNanGJfK .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-f7UyXpk7mNanGJfK .arrowheadPath{fill:#333333;}#mermaid-svg-f7UyXpk7mNanGJfK .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-f7UyXpk7mNanGJfK .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-f7UyXpk7mNanGJfK .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-f7UyXpk7mNanGJfK .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-f7UyXpk7mNanGJfK .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-f7UyXpk7mNanGJfK .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-f7UyXpk7mNanGJfK .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-f7UyXpk7mNanGJfK .cluster text{fill:#333;}#mermaid-svg-f7UyXpk7mNanGJfK .cluster span{color:#333;}#mermaid-svg-f7UyXpk7mNanGJfK div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-f7UyXpk7mNanGJfK .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-f7UyXpk7mNanGJfK rect.text{fill:none;stroke-width:0;}#mermaid-svg-f7UyXpk7mNanGJfK .icon-shape,#mermaid-svg-f7UyXpk7mNanGJfK .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-f7UyXpk7mNanGJfK .icon-shape p,#mermaid-svg-f7UyXpk7mNanGJfK .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-f7UyXpk7mNanGJfK .icon-shape rect,#mermaid-svg-f7UyXpk7mNanGJfK .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-f7UyXpk7mNanGJfK .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-f7UyXpk7mNanGJfK .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-f7UyXpk7mNanGJfK :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

否

是

初始化并查集结构

遍历grid

当前格子为1?

跳过

检查上下左右相邻节点

合并相邻陆地节点

更新集合数量

返回岛屿数量

Java代码实现

class Solution {
public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
UnionFind uf = new UnionFind(grid);
int[][] dirs = {{1,0},{–1,0},{0,1},{0,–1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
for (int[] d : dirs) {
int nx = i + d[0];
int ny = j + d[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1') {
uf.union(i * cols + j, nx * cols + ny);
}
}
}
}
}
return uf.getCount();
}
}

class UnionFind {
int[] parent;
int count;
int rows, cols;

public UnionFind(char[][] grid) {
rows = grid.length;
cols = grid[0].length;
parent = new int[rows * cols];
count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
int id = i * cols + j;
parent[id] = id;
count++;
}
}
}
}

public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
count—;
}
}

public int getCount() {
return count;
}
}

复杂度分析

七、总结对比