总而言之
BFS的方法对于静态的图的联通块问题比较好解
Union Find 解决动态的图的联通块的问题
1. BFS
TIME: O(MxN)
Space: O(min(M,N)) because in worst case where the grid is filled with lands, the size of the queue can grow up to min(M,N)
class Point { int x; int y; public Point(int x, int y){ this.x = x; this.y = y; }} class Solution { public int numIslands(char[][] grid) { if(grid.length == 0) return 0; int n = grid.length; int m = grid[0].length; //bfs int island = 0; int[] dx = new int[]{0,0,1,-1}; int[] dy = new int[]{1,-1,0,0}; for(int i = 0; i< n; ++i){ for(int j = 0 ; j< m; ++j){ if(grid[i][j] == '1'){ island ++; grid[i][j] = '0'; Queue queue = new LinkedList<>(); queue.offer(new Point(i, j)); while(!queue.isEmpty()){ Point current = queue.poll(); for(int index = 0 ; index < 4 ; ++index){ int nextX = dx[index] + current.x; int nextY = dy[index] + current.y; if(valid(nextX,nextY, grid)){ queue.offer(new Point(nextX,nextY)); grid[nextX][nextY] = '0'; } } } } } } return island; } private boolean valid(int x, int y, char[][] grid){ if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length){ return false; } return (grid[x][y] == '1'); }} 2. DFS
TIME: O(MxN)
Space: O(M+N) worst case that the grid map is filled with lands where DFS goes by M \times NM×N deep
public int numIslands(char[][] grid) { int n = grid.length; if(n == 0) return 0; int m = grid[0].length; int island = 0; for(int i = 0; i < n; ++i){ for(int j = 0 ; j < m; ++j){ if(grid[i][j] == '1'){ island ++; grid[i][j] = '0'; dfs(grid, i, j); } } } return island; } private void dfs(char[][] grid, int x, int y){ int[] dx = new int[]{0,0,1,-1}; int[] dy = new int[]{1,-1,0,0}; for(int i = 0; i < 4; ++i){ int nextX = dx[i] + x; int nextY = dy[i] + y; if(valid(nextX, nextY, grid)){ grid[nextX][nextY] = '0'; dfs(grid, nextX, nextY); } } } private boolean valid(int x, int y, char[][] grid){ if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length){ return false; } return (grid[x][y] == '1'); }
3. Union Find
Time: O(MxN)
Space: O(M×N) as required by UnionFind data structure
首先是Union Find 的定义
Point 要override hashcode和equals两个 ** 用Objects自带的方法比较好
class Point{ int x; int y; public Point(int x, int y){ this.x = x; this.y = y; } public int hashCode(){ return Objects.hash(this.x, this.y); } public boolean equals(Object p){ Point other = (Point)p; return Objects.equals(other.x, this.x) && Objects.equals(other.y, this.y); }}class UnionFind{ Map map; int size; public UnionFind(char[][] grid){ map = new HashMap<>(); size = 0; for(int i = 0 ; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(grid[i][j] == '1'){ map.put(new Point(i,j),new Point(i,j)); size ++; } } } } public void union(Point p1, Point p2){ size--; map.put(findRoot(p1), findRoot(p2)); } public Point findRoot(Point p){ if(map.get(p) != p){ map.put(p, findRoot(map.get(p))); } return map.get(p); } public boolean sameUnion(Point p1, Point p2){ return findRoot(p1) == findRoot(p2); }} class Solution { public int numIslands(char[][] grid) { UnionFind uf = new UnionFind(grid); for(int i = 0; i < grid.length; ++i){ for(int j = 0 ; j < grid[0].length; ++j){ if(grid[i][j] == '1'){ dfs(grid, i, j, uf); } } } return uf.size; } private void dfs(char[][] grid, int x, int y,UnionFind uf){ int[] dx = new int[]{0,0,1,-1}; int[] dy = new int[]{1,-1,0,0}; for(int i = 0; i < 4; ++i){ int nextX = dx[i] + x; int nextY = dy[i] + y; if(valid(nextX, nextY, grid) && !uf.sameUnion(new Point(nextX,nextY), new Point(x,y))){ uf.union(new Point(nextX,nextY), new Point(x,y)); dfs(grid, nextX, nextY, uf); } } } private boolean valid(int x, int y, char[][] grid){ if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length){ return false; } return (grid[x][y] == '1'); }}