深度優(yōu)先搜索（Depth First Search，DFS）

主要思想：不撞南墻不回頭

深度優(yōu)先遍歷的主要思想就是：首先以一個(gè)未被訪問過的頂點(diǎn)作為起始頂點(diǎn)，沿當(dāng)前頂點(diǎn)的邊走到未訪問過的頂點(diǎn)；當(dāng)沒有未訪問過的頂點(diǎn)時(shí)，則回到上一個(gè)頂點(diǎn)，繼續(xù)試探訪問別的頂點(diǎn)，直到所有的頂點(diǎn)都被訪問。

沿著某條路徑遍歷直到末端，然后回溯，再沿著另一條進(jìn)行同樣的遍歷，直到所有的頂點(diǎn)都被訪問過為止。

這道題時(shí)間和空間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'; //表示已經(jīng)走過 
        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
    } 
}

廣度優(yōu)先搜索（Breadth First Search, BFS）

主要思想：層層遞進(jìn)

首先以一個(gè)未被訪問過的頂點(diǎn)作為起始頂點(diǎn)，訪問其所有相鄰的頂點(diǎn)，然后對每個(gè)相鄰的頂點(diǎn)再訪問它們相鄰的未被訪問過的頂點(diǎn)，直到所有頂點(diǎn)都被訪問過，遍歷結(jié)束

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參考例子
我還需要總結(jié)一下。