岛屿数量问题：DFS、BFS与并查集算法解析-云帆数科

1. 岛屿数量问题解析今天我们来聊聊这个经典的算法问题——岛屿数量。第一次看到这个题目时你可能觉得它很简单但深入思考后会发现其中蕴含着不少值得探讨的细节。这个问题不仅常见于技术面试在实际应用中也有很多场景比如图像处理中的连通区域分析、地理信息系统中的岛屿识别等。2. 问题定义与理解2.1 问题描述给定一个由1(陆地)和0(水)组成的二维网格计算网格中岛屿的数量。岛屿被水包围并且通过水平或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边都被水包围。示例输入[ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出32.2 关键概念解析理解这个问题需要明确几个关键点网格表示通常用二维数组表示每个元素要么是1要么是0相邻定义仅考虑上下左右四个方向不考虑对角线岛屿定义一组相邻的1组成一个岛屿3. 解决方案设计3.1 基本思路解决这个问题的核心思路是遍历整个网格当遇到一个1时就找到了一个岛屿然后需要把这个岛屿的所有相邻1都标记为已访问避免重复计数。3.2 算法选择主要有两种经典算法可以解决这个问题深度优先搜索(DFS)广度优先搜索(BFS)两种方法的时间复杂度都是O(M×N)其中M和N分别是网格的行数和列数。4. 深度优先搜索实现4.1 算法步骤遍历网格中的每个单元格当遇到1时岛屿计数加1从这个1开始进行DFS将所有相连的1标记为0(表示已访问)继续遍历直到网格结束4.2 代码实现def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count4.3 复杂度分析时间复杂度O(M×N)每个单元格最多被访问两次空间复杂度O(M×N)最坏情况下递归栈的深度5. 广度优先搜索实现5.1 算法步骤遍历网格中的每个单元格当遇到1时岛屿计数加1初始化一个队列将当前1的位置加入队列从队列中取出位置检查其四个邻居如果是1则标记为0并加入队列重复直到队列为空5.2 代码实现from collections import deque def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 grid[r][c] 0 queue deque([(r, c)]) while queue: row, col queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc row dr, col dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 0 queue.append((nr, nc)) return count5.3 复杂度分析时间复杂度O(M×N)空间复杂度O(min(M,N))队列的最大长度6. 并查集解决方案6.1 并查集简介并查集(Disjoint Set Union)是一种数据结构用于处理不相交集合的合并与查询问题。它支持两种操作Find查找元素所属集合Union合并两个集合6.2 算法思路初始化并查集每个1的单元格都是一个独立集合遍历网格对于每个1检查其右侧和下侧的邻居如果邻居也是1则合并这两个集合最后统计独立集合的数量6.3 代码实现class UnionFind: def __init__(self, grid): rows, cols len(grid), len(grid[0]) self.parent [i for i in range(rows * cols)] self.count sum(grid[r][c] 1 for r in range(rows) for c in range(cols)) 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: self.parent[rootx] rooty self.count - 1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for r in range(rows): for c in range(cols): if grid[r][c] 1: index r * cols c if r 1 rows and grid[r1][c] 1: uf.union(index, (r1)*cols c) if c 1 cols and grid[r][c1] 1: uf.union(index, r*cols c1) return uf.count6.4 复杂度分析时间复杂度O(M×N×α(M×N))其中α是反阿克曼函数增长极慢空间复杂度O(M×N)7. 性能比较与选择7.1 三种方法对比方法时间复杂度空间复杂度适用场景DFSO(M×N)O(M×N)网格较小递归深度可控BFSO(M×N)O(min(M,N))网格较大避免递归栈溢出并查集O(M×N×α(M×N))O(M×N)需要动态处理岛屿合并7.2 选择建议面试场景推荐DFS或BFS代码简洁易懂大规模网格BFS更优避免递归栈溢出动态岛屿合并并查集是唯一选择8. 常见问题与优化8.1 边界条件处理空输入直接返回0单行或单列网格需要特殊处理吗不需要通用解法适用全0或全1的情况需要正确处理8.2 优化技巧原地修改直接修改输入网格来标记访问状态提前终止如果已经访问所有1可以提前结束并行处理对于极大网格可以考虑并行算法8.3 常见错误忘记标记已访问的单元格导致无限循环错误处理网格边界导致数组越界对角线相邻误认为属于同一岛屿9. 实际应用场景9.1 图像处理在图像处理中岛屿数量问题可以用于连通区域分析目标检测图像分割9.2 地理信息系统真实岛屿计数湖泊识别地块划分9.3 社交网络寻找独立用户群体社区发现网络连通性分析10. 变种问题10.1 最大岛屿面积不仅计算岛屿数量还要找出最大岛屿的面积10.2 封闭岛屿数量统计完全被水(0)包围的岛屿数量10.3 不同形状岛屿识别并统计不同形状的岛屿数量11. 个人实现心得在实际编码实现时我有几点经验分享优先考虑DFS实现代码通常更简洁使用BFS时注意队列的实现方式Python中deque比list效率更高并查集的路径压缩优化能显著提升性能测试时要考虑极端情况如全1、全0、单行、单列等在标记访问状态时可以直接修改输入数组避免额外空间开销

企业数字化 ERP 产品动态

相关推荐

从10类实体到21个BIO标签：BERT微调中文NER对齐实战

简介：面向自然语言处理初学者与需要落地中文实体抽取的开发者，这份PDF文档围绕BERT预训练模型微调完成命名实体识别任务展开，属于入门到实践的过渡型笔记。内容先界定地址、书籍、公司、游戏、政府、电影、姓名、组织、职位、场景共10类实体&… · 2026/11/2 21:45:26

GitLab、Bitbucket与GitPuk代码管理平台深度对比

1. 代码管理工具选型困境与核心需求刚接手一个新项目时，团队最头疼的问题之一就是选择哪个代码管理平台。三年前我们团队从SVN迁移到Git时，面对GitLab、Bitbucket和GitPuk这三个主流选择，整整争论了两周都没结论。最终我们做了件很"极客… · 2026/11/2 21:45:26

Git代码暂存机制详解与应用实践

1. 为什么我们需要代码暂存机制在多人协作的软件开发中，Git分支管理是日常工作的重要组成部分。我经历过无数次这样的场景：正在feature分支上开发新功能，突然线上出现紧急bug需要立即修复。这时候你会面临一个两难选择——要么草草提交未完成… · 2026/11/2 21:45:26

JPA @GeneratedValue 四种主键生成策略深度解析与选型指南

1. 为什么一个主键生成策略值得单独写一篇第一次接触 JPA 的人，十有八九会在GeneratedValue上栽跟头。表面上看它只是个给主键“自动填数”的注解，写上去就能跑，但真到了生产环境，序列跳号、批量插入性能骤降、多实例部署主键冲突… · 2026/11/2 22:30:54

Java期末选择题高频陷阱与答题规则全解析

简介：这份文档面向河北工业大学修读 Java 课程、准备期末考试的学生，聚焦课堂知识点梳理与题型训练，帮助读者在复习阶段快速定位重点、检验掌握程度。包内共 1 个 doc 文件，整体约 68KB，以文字版复习题为主体&#xff… · 2026/11/2 22:30:54

LLM生成工业级嵌入式控制软件的本体驱动方法

1. 项目概述：当大语言模型真正开始“写控制软件”而不是“聊控制软件”ICRA 2026上这个标题一出来，我第一时间在实验室白板上画了个三层结构图：最底下是真实产线上的AGV小车、机械臂、无人叉车组成的物理集群；中间层是传统运筹优化… · 2026/11/2 22:30:54

用户反馈体系搭建指南：从收集到闭环的实操方法

做产品的人都有一个共同的痛：用户嘴上说的、手上做的、心里想的，往往是三件完全不同的事。尤其像 Cherry Studio 这类面向多场景的桌面客户端工具，用户群体横跨技术爱好者、内容创作者、日常办公人群，反馈渠道又散落在社群、邮件、… · 2026/11/2 22:29:53

工具类产品用户反馈体系：从触点设计到迭代决策的闭环实践

1. 用户反馈体系的整体设计与思路拆解做工具类产品的人都有一个共同的痛：用户嘴上说的、手上做的、心里想的，往往是三件完全不同的事。Cherry Studio 这类面向知识工作者的桌面客户端产品，用户群体偏专业、偏重度，反馈渠道天然分散… · 2026/11/2 22:29:53

2025大模型投资复盘：推理引擎、Agent与微调实战

1. 从投资视角看大模型赛道的真实体感2025年这一年，如果只用一个词来概括大模型领域的投资感受，我会选“分化”。年初的时候，身边不少朋友还在纠结要不要追多模态的早期项目，到了年中，话题已经全面转向Agent落地和推理… · 2026/11/2 22:28:53

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

雷达信号调制技术解析：从LFM到伪线性调频原理与应用

基于MAX14431与TM4C123的工业SPI隔离电路设计全攻略

PLFM_RADAR：相位线性调频雷达信号处理框架

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

岛屿数量问题：DFS、BFS与并查集算法解析

相关推荐

了解更多？预约专属演示