DFS/BFS/UN - LC200 Number of Islands

深度优先搜索（Depth First Search，DFS）

主要思想：不撞南墙不回头

深度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问。

沿着某条路径遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。

这道题时间和空间O(m*n)

class Solution {
    public int numIslands(char[][] grid) {
        if(grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (grid[i][j] != '1' ) continue;
                ++res;
                dfs(grid, i, j, m-1, n-1);
            }
        }
        return res;
    }
      
    public void dfs(char[][] grid, int i, int j, int m, int n) {  
        if (i < 0 || i > m || j < 0 || j > n || grid[i][j] != '1') return;
        grid[i][j] = '2'; //表示已经走过 
        dfs(grid, i - 1, j, m, n); //up 
        dfs(grid, i + 1, j, m, n);  //down
        dfs(grid, i, j - 1, m, n);  //left
        dfs(grid, i, j + 1, m, n);  //right
    } 
}

广度优先搜索（Breadth First Search, BFS）

主要思想：层层递进

首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束

public class Solution {
    public int numIslands(char[][] grid) {
        if(grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (grid[i][j] == '1' ) {
                    LinkedList<Point> queue = new LinkedList<Point>();
                    visited(grid, i, j, queue);
                    ++res;
                    bfs(grid, queue, m, n);
                }
                
            }
        }
        return res;
    }
      
    private void bfs(char[][] grid, LinkedList<Point> queue, int m, int n){
        while(!queue.isEmpty()) {  
            Point point = queue.poll();
            int code = point.x - 1;
            if(code >= 0 && grid[code][point.y] == '1') visited(grid, code, point.y, queue);//up
            code = point.x + 1;
            if(code < m && grid[code][point.y] == '1') visited(grid, code, point.y, queue);//down
            code = point.y - 1;
            if(code >= 0 && grid[point.x][code] == '1') visited(grid, point.x, code, queue);//left
            code = point.y + 1;
            if(code < n && grid[point.x][code] == '1') visited(grid, point.x, code, queue);//right
            
        } 
    }
    
    private void visited(char[][] grid, int i, int j, LinkedList<Point> queue){
        Point point = new Point(i, j);
        queue.offer(point);  
        grid[i][j] = '2'; //mark visited 
    }
    
    public class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
}

union-find 方法

UN参考例子
我还需要总结一下。