三维网格最大岛屿体积：DFS、BFS与并查集解法全解析

“最大岛屿体积”这个标题第一眼看上去像是力扣题库里那两道“最大岛屿面积”的升级版。但真正上手之后你会发现把“面积”换成“体积”并不只是多一个维度那么简单三维连通性的定义、遍历顺序、内存占用、递归深度每一项都可能让一个原本很顺的解法直接翻车。先说清楚这是在解决什么问题。所谓“最大岛屿体积”是在一个三维二值网格里每个位置可能是 0 或 1把所有值为 1 且六方向相邻的格子视作一个整体这个整体包含的格子数就是体积我们的目标是找出所有连通块中格子数量的最大值。如果你在准备算法面试它是最典型的连通区域搜索问题从二维向三维的延伸如果你在写工程代码CT 影像里的器官与病灶体积测量、地质数据里的矿藏范围估算、三维点云里的连通簇分析都是同一套逻辑在不同场景下的马甲。这篇文章适合两类人一类是刚学完 DFS/BFS 想进阶的算法学习者另一类是手头正好有体素数据要算连通体积的工程师。1. 题目到底在问什么体积和面积不是一回事1.1 从二维面积到三维体积的变化二维的“最大岛屿面积”是这样的给定一个 m×n 的 0/1 矩阵1 表示陆地0 表示水上下左右四个方向连通的 1 构成一座岛屿返回最大岛屿的面积。这个问题的核心难点只有一个如何高效地找出所有连通块并统计大小。常规解法就是扫描每个格子遇到没访问过的 1 就启动一次 DFS 或 BFS把整个连通块标记完顺手记个数。三维的“最大岛屿体积”看起来只是把 m×n 换成 x×y×z把二维坐标 (i, j) 换成三维坐标 (i, j, k)把四个方向换成六个方向。但实际写起来有三处和二维有本质区别。第一索引复杂度上升。二维只要处理 i 和 j 两个下标三维所有循环、越界判断、方向偏移都要同步加一维写错索引的概率翻倍。我见过不少同事把三维坐标写进二维的越界判断里测试数据小的时候看不出来一旦碰到边界坐标就报 IndexError。第二内存布局和访问模式变了。三维数据无论是用 Python 的嵌套 list 还是 C 风格的连续数组最内层维度通常是 z 轴。遍历时如果最外层循环选得不好缓存命中率会明显下降。算法题里可能感受不深但工程上一块 512×512×512 的体数据随便一跑就是上亿次访问缓存 miss 会把时间直接拖到不可接受。第三visited 数组的维护成本变高。二维的 visited 矩阵很小三维一个标记数组的大小就是 X×Y×Z。Python 里如果再用嵌套 list 存布尔值实际占用的内存会比想象中大得多这点后面我会专门展开讲。1.2 六连通与二十六连通怎么选三维网格里一个格子周围到底有多少邻居取决于你如何定义“相邻”。这是写代码前必须确认的第一件事。最常用的是六连通只算共享一个面的六个方向邻居也就是上下左右前后。这个定义最接近物理上的“接触”也是 CT、MRI 这类体数据里最常用的连通规则。好处是判断简单、遍历量小缺点是标准严格斜着贴在一起的区域会被认为不连通。还有二十六连通把共享边和共享角的邻居都算进来一共 26 个方向。在三维点云、游戏体素世界里偶尔会用到因为有些稀疏数据里你希望把“斜插”过来的体素也归到同一个簇。另有十八连通共享面或共享边的 18 个方向介于两者之间但实际用得少。具体怎么选取决于业务定义。算法题里如果题目没写默认是六连通。我在实际工程里踩过一个坑最开始为了省事把二维的四方向代码直接改成三维六方向结果测试数据里两个器官明明物理相连代码却算成了两个岛屿。原因就是二维里的“上下左右”在三维视角下漏掉了 z 轴方向而 z 轴方向上的相邻关系恰恰是两个器官连通的关键。反过来如果你用了二十六连通稀疏噪声点很容易把不该连的东西串在一起导致体积虚高。所以动手前先把连通定义确认清楚比优化算法更重要。2. 三种主流解法DFS、BFS、并查集怎么选2.1 先给结论三种方案的取舍对照DFS、BFS、并查集都能解决连通块统计问题但适用场景并不一样。我用一张表把关键差异列出来。方案实现复杂度空间占用典型适用场景DFS递归最低低但递归栈有爆栈风险小数据、快速原型DFS迭代栈中等较低中大型数据避免递归爆栈BFS队列中等较高队列可能很大层级遍历、需要记录距离并查集较高较高需要多次查询连通关系、批量合并从面试角度面试官通常希望看到你至少能实现 DFS 或 BFS 中的一种并说清两者的差异。从工程角度如果数据量不大三者都行如果数据量到了千万个 voxel 的级别我一般选迭代 DFS 或 BFS纯 Python 写并查集会因为常数因子较大而偏慢。这里多说一句“为什么推荐迭代 DFS”。二维题里大家喜欢递归 DFS因为代码短几行就能写明白。但到了三维递归深度最坏可能等于整个连通块的体积假设有一个 100×100×100 的实心块递归深度就是 100 万层Python 默认递归限制只有 1000几乎必然栈溢出。所以三维场景我一律推荐迭代栈 DFS 或 BFS递归只在数据规模很小时使用。2.2 迭代 DFS 的实现与细节递归会爆栈那迭代版本怎么处理思路很简单手动维护一个栈。遇到一个未访问的陆地体素时把它压栈然后循环弹栈、计数、再把六个方向的未访问邻居压进去。关键细节在于在压栈前标记 visited而不是在弹栈时再标记。否则同一个节点可能会被多个邻居重复压入栈既浪费内存又浪费时间。这两个写法的区别在二维题里不明显在三维大块实体里会非常致命。直接看代码。def max_volume_volume_dfs(grid): if not grid or not grid[0] or not grid[0][0]: return 0 X, Y, Z len(grid), len(grid[0]), len(grid[0][0]) visited [[[False for _ in range(Z)] for _ in range(Y)] for _ in range(X)] max_vol 0 directions [ (1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1), ] def dfs(sx, sy, sz): stack [(sx, sy, sz)] visited[sx][sy][sz] True volume 0 while stack: x, y, z stack.pop() volume 1 for dx, dy, dz in directions: nx, ny, nz x dx, y dy, z dz if ( 0 nx X and 0 ny Y and 0 nz Z and not visited[nx][ny][nz] and grid[nx][ny][nz] 1 ): visited[nx][ny][nz] True stack.append((nx, ny, nz)) return volume for i in range(X): for j in range(Y): for k in range(Z): if grid[i][j][k] 1 and not visited[i][j][k]: max_vol max(max_vol, dfs(i, j, k)) return max_vol几个值得注意的点方向列表定义成模块级常量会更好避免每次启动遍历时重复构造。空值判断not grid or not grid[0] or not grid[0][0]是为了防止输入为空多维数组时报错。visited 用列表推导式生成不要用[[[False] * Z] * Y] * X这种写法后者会把内层列表的引用复制多份修改一个位置会连带影响其他层。2.3 BFS 的实现与细节BFS 只是把栈换成队列遍历顺序从深度优先变成层级优先。对统计体积这个问题来说DFS 和 BFS 的结果完全一样区别主要在空间表现。BFS 用队列这里要用collections.deque不要用 list 的 pop(0)后者是 O(n) 的时间复杂度数据量大时会非常痛苦。from collections import deque def max_volume_volume_bfs(grid): if not grid or not grid[0] or not grid[0][0]: return 0 X, Y, Z len(grid), len(grid[0]), len(grid[0][0]) visited [[[False for _ in range(Z)] for _ in range(Y)] for _ in range(X)] max_vol 0 directions [ (1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1), ] for i in range(X): for j in range(Y): for k in range(Z): if grid[i][j][k] 1 and not visited[i][j][k]: q deque([(i, j, k)]) visited[i][j][k] True volume 0 while q: x, y, z q.popleft() volume 1 for dx, dy, dz in directions: nx, ny, nz x dx, y dy, z dz if ( 0 nx X and 0 ny Y and 0 nz Z and not visited[nx][ny][nz] and grid[nx][ny][nz] 1 ): visited[nx][ny][nz] True q.append((nx, ny, nz)) max_vol max(max_vol, volume) return max_vol实测下来BFS 和 DFS 在时间复杂度上没有本质差别但 BFS 的队列在“胖”连通块上会比较大。DFS 栈里保留的只是单条路径的分支节点整体内存占用通常更好。如果连通块是细长条形的DFS 栈会很小BFS 队列也会很小如果连通块是实心立方体BFS 的队列峰值会大一些。所以纯看空间我更喜欢迭代 DFS。2.4 并查集的实现与细节并查集的思路和 DFS/BFS 完全不同。它先把每个陆地体素都当成一个独立的岛屿然后遍历所有相邻陆地把它们合并到同一个集合里最后查每个集合的大小。这个方案的优势在于一次建立连通关系后可以随时回答“某个体素属于哪个岛屿”“这个岛屿有多大”不需要重新遍历网格。缺点是每个点和每条边都要单独操作常数因子较大在小数据上反而不一定跑得快。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] def max_volume_volume_union_find(grid): if not grid or not grid[0] or not grid[0][0]: return 0 X, Y, Z len(grid), len(grid[0]), len(grid[0][0]) uf UnionFind(X * Y * Z) def idx(x, y, z): return (x * Y y) * Z z directions [ (1, 0, 0), (0, 1, 0), (0, 0, 1), ] for x in range(X): for y in range(Y): for z in range(Z): if grid[x][y][z] 0: continue for dx, dy, dz in directions: nx, ny, nz x dx, y dy, z dz if ( 0 nx X and 0 ny Y and 0 nz Z and grid[nx][ny][nz] 1 ): uf.union(idx(x, y, z), idx(nx, ny, nz)) best 0 for x in range(X): for y in range(Y): for z in range(Z): if grid[x][y][z] 1: best max(best, uf.size[uf.find(idx(x, y, z))]) return best并查集版本里有一个小优化合并时只遍历正方向也就是 (1,0,0)、(0,1,0)、(0,0,1)。这样每条相邻边只会被处理一次不会重复合并。因为整个遍历会覆盖所有体素双向遍历完全是冗余的。很多不熟悉并查集的人会问为什么要用按大小合并而不是随便挂原因很简单如果不做任何优化并查集的树可能会退化成长链find 的复杂度会从近似 O(1) 退化到 O(n)。按大小合并能保证树高始终是 O(log n)配合路径压缩实际使用中几乎可以认为是常数时间。3. 完整实操从构造数据到函数调用3.1 构造一个可验证的三维网格写代码之前先准备一份能验证结果的小数据。我习惯手动构造一个 4×4×4 的网格里面放两个岛屿一个体积是 3一个体积是 5然后用三种解法分别跑一遍保证输出一致。grid [[[0 for _ in range(4)] for _ in range(4)] for __ in range(4)] # 岛屿 A体积 3 grid[0][0][0] 1 grid[0][0][1] 1 grid[0][1][0] 1 # 岛屿 B体积 5 grid[2][2][2] 1 grid[2][2][3] 1 grid[2][3][2] 1 grid[3][2][2] 1 grid[2][3][3] 1检查一下岛屿 B 的连通性。从 (2,2,2) 出发(2,3,2) 是 y 方向邻居(3,2,2) 是 x 方向邻居(2,2,3) 是 z 方向邻居。再看多出来的 (2,3,3)它和 (2,3,2) 在 z 方向相邻也和 (2,2,3) 在 y 方向相邻。所以五个点确实通过六连通关系全部串联在一起体积是 5。调用一下print(max_volume_volume_dfs(grid)) print(max_volume_volume_bfs(grid)) print(max_volume_volume_union_find(grid))三个函数都应该输出 5。3.2 完整代码与调用示例上面三个函数加在一起已经有几十行实际使用时我一般把三个版本放在同一个文件里用函数名后缀区分方便在测试数据集上做交叉验证。交叉验证非常重要尤其是当你有现成的大网格、结果又没法靠肉眼判断时DFS、BFS、并查集三个独立实现跑出相同结果基本可以确定逻辑没有大问题。调用时还有一个实际经验如果网格特别大把输入数据转换成 numpy 数组会提升访问速度。Python 的嵌套 list 在每次索引取值时都有额外开销换成 numpy 的三维数组后纯遍历的常数会小很多。但要注意visited 数组如果也想用 numpy类型要选对np.zeros((X, Y, Z), dtypebool)比嵌套 list 省内存得多。3.3 复杂度与内存估算时间复杂度上三种方案都是 O(X×Y×Z)因为每个体素最多被访问常数次。谁都不会更慢一个数量级差距只在常数因子。空间复杂度就有意思了。DFS/BFS 需要 visited 数组和栈或队列visited 数组本身是 O(X×Y×Z)。并查集的 parent 和 size 数组加起来也是 O(X×Y×Z)。所以理论上的空间复杂度都一样但实际内存占用差别很大。拿 256×256×256 的网格举例总共 1600 多万个 voxel。如果 visited 用 Python 嵌套 list 存布尔值每个位置存的是一个对象的引用8 字节起步整体大约 128MB加上列表本身的开销轻松超过 150MB。如果换成 numpy 的 bool 数组每个元素只有 1 字节只要 16MB。并查集的 parent 数组如果存 intPython int 对象又是 28 字节起步内存压力反而更大。所以我在工程里处理真实体数据时visited 一律改用bytearray或 numpy 数组。算法题里怎么简单怎么写工程里怎么省内存怎么写。3.4 如果你不允许修改原数据有人为了省掉 visited 数组会直接把访问过的 1 改成 0也就是所谓的“淹没法”。这个技巧在二维题里很好用代码省一行内存省一块。但工程上有个大坑如果调用方还需要保留原始网格做别的分析比如同时计算表面积、统计密度你改完数组原始数据就没了。我的建议是分场景算法题刷题阶段可以用淹没法代码更短。工程代码里除非你非常确定这个数组是一次性的、后续没有复用需求否则老老实实用 visited。即使是淹没法三维场景也要小心不要在处理过程中把整个实心块改成 0 后又需要在外部统计时发现数据被破坏了。我自己有一次在预处理流水线里用了淹没法结果后面一个模块要读同一份体数据算加权质心读到的全是 0定位问题花了一个晚上。自此之后凡是共享数据我一律加 visited。4. 我实际踩过的几个坑4.1 递归爆栈这个坑在 2.2 里已经提过但值得再单独强调一次。二维岛屿面积题里递归 DFS 是最常见的解法很多人形成惯性直接套到三维上。我在一个 200×200×200 的随机网格上做过测试递归深度一旦超过几百层Python 就会报 RecursionError。而 200 的立方体里随便一个稍大的连通块就能轻松达到几千的递归深度。处理方式很简单把递归改成迭代栈就是 2.2 的代码。改完之后体积计算从“经常崩溃”变成“稳定跑完”。4.2 索引写错三维坐标写错是个极其隐蔽的坑。最常见的情况是越界判断里漏了 z 轴或者把 x、y、z 的顺序搞混。比如把条件写成0 nx X and 0 ny Y忘了检查0 nz Z小数据不会出错但一旦碰到 z 轴边界立刻 IndexError。还有一种更隐蔽的循环变量用了同一个字母。比如三个循环都用 i内层循环把外层 i 覆盖了。这种问题在二维代码里不太会出现因为习惯上会用 i、j 区分三维多了一个变量取名容易乱。我的习惯是统一用x, y, z方向偏移用dx, dy, dz语义清楚不容易混。4.3 内存开销失控前面提到Python 嵌套 list 的 visited 数组在 256×256×256 的规模下就可能吃掉 150MB 以上。如果你同时还要维护一个栈或队列内存很容易翻倍。实测下来最稳的组合是numpy 布尔数组当 visited迭代 DFS 栈里只存坐标元组。坐标元组也有开销但栈的峰值通常远小于 visited 数组本身。如果连坐标元组的开销都嫌大还有一个思路把三维坐标编码成一个整数再压栈比如code (x * Y y) * Z z弹栈时再解码。这样栈里存的是 int虽然 Python int 本身也有开销但比元组小一些。缺点是代码可读性下降。我一般在内存紧张时才会这么做。4.4 边界判断漏掉三维的越界判断是每个方向都要检查这个已经说过了。还有一个容易被忽略的是空值判断。如果输入是空的列表或者某一行是空的直接访问grid[0][0][0]就会 IndexError。所以函数开头那一行空值保护不是可有可无的装饰是必须的。我在测试时经常用极端输入来验证边界全 0 的网格、全 1 的网格、单点岛屿、矩形长条岛屿、只有一个维度大小为 1 的“扁平网格”。扁平网格很有意思它本质上退化成二维问题但三维代码应该仍然能正确运行。比如 1×4×4 的网格六连通下其实只剩上下左右四个方向前后方向因为 X1 而不存在代码里的越界判断会自然过滤掉这些方向。5. 工程场景落地从算法题到真实数据5.1 医学影像里的体积测量医学影像里最常见的就是 CT 序列。一次胸部 CT 扫描会产生几百张二维切片堆叠起来就是一个三维体数据。医生想看的肺结节体积、肿瘤负荷、器官体积本质上都是“最大岛屿体积”或者“多个连通块体积之和”。但工程实现上有几个和算法题不一样的难点体数据往往不是严格的 0/1而是 Hounsfield 单位CT 值范围在 -1000 到 1000 以上。要先做阈值分割把目标组织提取成二值掩膜再计算体积。分割这一步做得不好后面体积算得再准也没意义。体素在三个方向的物理间隔可能不一样。CT 的层间距经常大于层内像素间距比如层面内是 0.5mm层间距是 1mm。这时候如果直接把体素数当作体积结果就偏了。正确的做法是真实体积 体素数 × 单个体素的物理体积也就是 dx × dy × dz。算法题里没人在乎单位但工程里必须换算。肺结节 5mm 和 8mm差出来的体积对治疗方案影响很大。5.2 点云数据和地质数据里的连通簇三维点云经过体素化之后会得到一个稀疏的三维网格。因为这个网格非常稀疏连通块通常不大DFS 和 BFS 都很快。但点云的噪声会导致伪连通一个孤立的噪声点如果和你关注的目标在 26 连通定义下“接触”体积就会虚高。这种情况下我倾向于先用形态学开运算把离散噪声去掉再做连通域分析。地质数据里也有类似需求比如矿体建模。钻孔数据插值后会生成矿物品位的三维体数据品位高于某个阈值的区域就是潜在矿体。矿体在空间上通常是不规则的连通块计算它的体积对储量估算影响很大。这里要注意的是矿体往往有多个离散块除了最大体积还需要统计所有大于某个阈值的块有时候还需要计算每个块的中心和边界。这些都可以在以“最大岛屿体积”为基础的算法上扩展。5.3 加权体积不只是数格子在某些场景里每个体素的价值并不是 1而是带有权重的。比如医学影像里每个体素可能带有密度值地质数据里每个体素可能带有品位值。这时候“体积”的定义可以扩展为一个连通块内所有体素权重之和。遍历逻辑完全不变唯一的变化是累加从volume 1变成volume grid[x][y][z]。如果你拿的是浮点权重要注意判断体素是否属于当前岛屿的条件也要调整。方法很简单准备一个同尺寸的 mask 数组mask 中为 1 的位置才是目标体素遍历时用 mask 做判断用权重数组做累加。# mask: 0/1 二值网格决定哪些体素属于岛屿 # weight: 浮点权重网格决定每个体素贡献多少体积 def max_weighted_volume(mask, weight): if not mask or not mask[0] or not mask[0][0]: return 0.0 X, Y, Z len(mask), len(mask[0]), len(mask[0][0]) visited [[[False for _ in range(Z)] for _ in range(Y)] for _ in range(X)] best 0.0 directions [ (1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1), ] for i in range(X): for j in range(Y): for k in range(Z): if mask[i][j][k] 1 and not visited[i][j][k]: stack [(i, j, k)] visited[i][j][k] True vol 0.0 while stack: x, y, z stack.pop() vol weight[x][y][z] for dx, dy, dz in directions: nx, ny, nz x dx, y dy, z dz if ( 0 nx X and 0 ny Y and 0 nz Z and mask[nx][ny][nz] 1 and not visited[nx][ny][nz] ): visited[nx][ny][nz] True stack.append((nx, ny, nz)) best max(best, vol) return best这个加权版本的适用面比纯 0/1 版本广得多。我之前在点云聚类项目里就是用 mask 存二值连通关系用 weight 存每个体素内部点的数量一次遍历同时算出“这个簇有多少个体素”和“这个簇实际包含多少个原始点”省下了后续大量统计代码。6. 从算法模板到自己的工具箱写到这里该分享的代码和细节都讲得差不多了。最后再分享一个我调试三维网格代码时常用的技巧。三维数据肉眼很难直接观察所以我调试时会把三维网格按 z 轴切片打印成二维矩阵一次看一层。比如 4×4×4 的网格就连续打印 4 个 4×4 的二维表。这样哪个位置的 1 连到了哪里一眼就能看清楚。我第一次调通三维体积算法靠的就是这个土办法。另外如果你经常要处理体数据建议把 DFS、BFS、并查集三个版本都保留在代码库里。它们功能等价但各有优势DFS 写起来最快BFS 结构最清晰并查集在需要多次查询连通关系的场景里不可替代。多几个版本不是冗余而是工具箱里的不同工具。“最大岛屿体积”这个题目看起来只是一个算法题但它把二维遍历、状态标记、内存控制、工程容错这些基础功全都串在了一起。能把这道题写得稳、写得快、写得省我相信你再回去写二维的岛屿面积基本就是降维打击了。