数据结构—图中统计岛屿数量
其实许多算法并不是脱离实际的，很多图像处理问题都会用到图算法。下面分享一个关于图问题，就是计算地图中在海洋中岛屿的数量，我们将地图抽象为一个网格，将地图通过网格划分为一个一个小区域。每一个小区域表示一个陆地或者海洋。
其中黄色表示 island
蓝色表示海洋
问题是要找出地图中岛屿的数量。
const grid = [ ['W','L','W','W','W'], ['W','L','W','W','W'], ['W','W','W','L','W'], ['W','W','L','L','W'], ['L','W','W','L','L'], ['L','L','W','W','W'], ] 复制代码
用于一个二维矩阵来表示，每一个格子对应一个坐标(行，列)。
基本思路
思路很重要，有了思路也就是有一个找到答案方向，只要方向正确怎么走都能到终点，只是时间多少的问题了。
主要是遍历所有格子，每一个格子通过行数和列数可以确定其位置，我们通过位置来区分不同格子。从左上角开始下逐行移动一个指针，当指针遇到 island 时候，然后遍历其邻接的单元格，其邻接单元中为陆地的单元，检查是否已经经过该单元，如果经过则直接返回 false 跳过，如果是没有经过的单元，则进行遍历，也就是深度优先遍历，将所有与该陆地可以连通的陆地单元遍历到并进行标记为访问过。
遍历所有单元格
for(let r = 0; r < grid.length; r +=1){ for(let c = 0; c < grid[0].length; c +=1){ if(explore(grid,r,c,visited) === true){ count +=1 } } } 复制代码遍历所有单元格
设置遍历的边界
const rowInbounds = 0 <= r && r < grid.length; const columnInbounds = 0 <= c && c < grid[0].length; if (!rowInbounds || !columnInbounds) return false 复制代码
为游走指针设置边界，然指针在地图范围内游走。也可以在下面遍历其邻接单元处进行控制指针移动范围，不过在开始控制显得更加优雅。
标记经过的单元格
const pos = r +',' + c; if(visited.has(pos)) return false; visited.add(pos); 复制代码
为了标记经过单元格可以利用 Set 来保存经过的单元格，单元格可以[r,c]，这样 Set就无法保持一致性。
完整代码
/** * r = # rows * c = # cols * Time:O(r c) * Space: O(rc) */ const grid = [ ['W','L','W','W','W'], ['W','L','W','W','W'], ['W','W','W','L','W'], ['W','W','L','L','W'], ['L','W','W','L','L'], ['L','L','W','W','W'], ] const islandCount = (grid) =>{ let count = 0 const visited = new Set(); for(let r = 0; r < grid.length; r +=1){ for(let c = 0; c < grid[0].length; c +=1){ if(explore(grid,r,c,visited) === true){ count +=1 } } } return count } const explore = (grid,r,c,visited) => { const rowInbounds = 0 <= r && r < grid.length; const columnInbounds = 0 <= c && c < grid[0].length; if (!rowInbounds || !columnInbounds) return false if(grid[r][c] === 'W') return false; const pos = r +',' + c; if(visited.has(pos)) return false; visited.add(pos); explore(grid,r -1, c,visited); explore(grid,r +1, c,visited); explore(grid,r, c-1,visited); explore(grid,r, c+1,visited); return true; } const res = islandCount(grid); console.log(res)
作者：ti138729
链接：https://juejin.cn/post/7021830005218869255