岛屿数量(DFS、BFS、并查集)
一、题目简介
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
（题目来源：力扣（LeetCode））
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
二、解决方法
1.DFS算法(Depth First Search，深度优先搜索算法)
package com.lxf.graph;
public class DFS {
//小岛数组行长度
private int ir;
//小岛数组列长度
private int ic;
public int numIslands(char[][] grid){
if (grid==null||grid.length==0) {
return 0;
}
//小岛数组行长度赋值
ir=grid.length;
//小岛数组列长度赋值
ic=grid[0].length;
//小岛数量
int numOfIsland=0;
for (int i = 0; i < ir; i++) {
for (int j = 0; j < ic; j++) {
if(grid[i][j]=='1'){
//小岛数量加1
++numOfIsland;
//深度遍历:将连通的1全部置为0，就是找第一个1相邻的1全集，也就是一个‘小岛’
dfs(grid,i,j);
}
}
}
return numOfIsland;
}
/**
* @param grid 小岛数组
* @param i 当前横坐标
* @param j 当前纵坐标
*/
private void dfs(char[][] grid, int i, int j) {
if(i<0||j<0||i>ir||j>ic||grid[i][j]=='0'){
//超出数组或者搜索到了0（这里就是以0为阻隔，也就是小岛周围的水）
return;
}
//搜索到一个1就直接置为0
grid[i][j]='0';
//上下左右深度搜索为1的相邻点
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
}
- BFS(Breadth First Search,广度优先搜索算法)
package com.lxf.graph;
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
//小岛数组行长度
int ir=grid.length;
//小岛数组列长度
int ic=grid[0].length;
//小岛数
int numOfIsland=0;
for (int i = 0; i < ir; i++) {
for (int j = 0; j < ic; j++) {
//遇到1就处理
if(grid[i][j]=='1'){
//小岛数+1，并且当前值要置为0
++numOfIsland;
grid[i][j]='0';
//广度优先搜索辅助队列
Queue<Integer> linkedList = new LinkedList<>();
//将当前位置的一维坐标加入队列（二维坐标转一维坐标）
linkedList.add(i*ic+j);
while (!linkedList.isEmpty()) {
//获取当前的坐标
int coordinate=linkedList.remove();
//获取当前横坐标
int row=coordinate/ic;
//获取当前纵坐标
int column=coordinate%ic;
//从当前坐标搜索上下左右为1的坐标（且不超出数组的范围）
//相当于从当前坐标搜索周边为1的坐标组成一个小岛，搜索到0后退出
if(row-1>=0&&grid[row-1][column]=='1'){
linkedList.add((row-1)*ic+column);
grid[row-1][column]='0';
}
if(row+1<ir&&grid[row+1][column]=='1'){
linkedList.add((row+1)*ic+column);
grid[row+1][column]='0';
}
if(column-1>=0&&grid[row][column-1]=='1'){
linkedList.add(row*ic+column-1);
grid[row][column-1]='0';
}
if(column+1<ic&&grid[row][column+1]=='1'){
linkedList.add(row*ic+column+1);
grid[row][column+1]='0';
}
}
}
}
}
return numOfIsland;
}
}
- 并查集
package com.lxf.graph;
public class MSL {
//小岛数组行长度
private int ir;
//小岛数组列长度
private int ic;
class UnionFind{
//统计小岛数
private int count;
//结点数组，用于指向当前结点的父结点
private int[] parent;
//存结点对应的‘秩’数组
private int[] rank;
public int getCount() {
return count;
}
/**
* 初始化方法
* @param grid 小岛数组
*/
public UnionFind(char[][] grid) {
count=0;
parent=new int[ir*ic];
rank=new int[ir*ic];
for (int i = 0; i < ir; i++) {
for (int j = 0; j < ic; j++) {
if(grid[i][j]=='1'){
//将结点数组中‘1’结点的父结点指向本身
parent[i*ic+j]=i*ic+j;
//统计所有的1数目
++count;
}
}
}
}
/**
* 合并方法
* @param x 合并第一个结点的下标
* @param y 合并第二个结点的下标
*/
public void union(int x,int y){
//找到第一个结点的父结点
int rootx=find(x);
//找到第二个结点的父结点
int rooty=find(y);
//只有当两个结点的父结点不同时才合并
//相同时说明已经合并完毕了
if (rootx!=rooty){
//下面三种情况都是执行操作：完全压缩路径以及按秩归并
if(rank[rootx]>rank[rooty]){
//如果第一个结点的父结点的秩大于第二个结点的父结点的秩
//直接将第二个结点的父结点等于第一个结点的父结点
parent[rooty]=rootx;
}else if(rank[rootx]<rank[rooty]){
//第一种情况的相反
parent[rootx]=rooty;
}else{
//如果两个秩相等
//第二个结点的父结点还是要等于第一个结点的父结点
//而且第一个结点的父结点的秩要+1
parent[rooty]=rootx;
rank[rootx]+=1;
}
//合并一次，小岛数量就要减一个
--count;
}
}
/**
* 找到当前结点的父结点方法
* @param i 当前结点的下标
* @return
*/
public int find(int i){
//如果当前结点不是指向自己，直接找他的父结点
if(parent[i]!=i){
parent[i]=find(parent[i]);
}
return parent[i];
}
}
public int numIslands(char[][] grid) {
if (grid==null||grid.length==0) {
return 0;
}
//小岛数组行长度赋值
ir=grid.length;
//小岛数组列长度赋值
ic=grid[0].length;
//并查集类对象
UnionFind uf = new UnionFind(grid);
for (int i = 0; i < ir; i++) {
for (int j = 0; j < ic; j++) {
//遇到1执行操作
if(grid[i][j]=='1'){
grid[i][j]='0';
//以当前1开始上下左右合并临近的1
if(i-1>=0&&grid[i-1][j]=='1'){
uf.union(i*ic+j,(i-1)*ic+j);
}
if(i+1<ir&&grid[i+1][j]=='1'){
uf.union(i*ic+j,(i+1)*ic+j);
}
if(j-1>=0&&grid[i][j-1]=='1'){
uf.union(i*ic+j,i*ic+j-1);
}
if(j+1<ic&&grid[i][j+1]=='1'){
uf.union(i*ic+j,i*ic+j+1);
}
}
}
}
return uf.getCount();
}
}