队列与BFS的联系，以及DFS

一、 BFS广度优先搜索是利用队列实现的，广度优先搜索需要对一个起始结点周围的所有相邻点进行广度优先搜索，它怎么“记住”这些相邻结点呢？靠队列，因为队列先进先出的思想也符合它先后找结点的顺序。

岛屿数量：
https://leetcode-cn.com/problems/number-of-islands/

这道题可以用BFS也可以用DFS，后者逻辑简单点但是时间复杂度较高。

https://leetcode-cn.com/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/
jyd题解：
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; 
            j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }
}

bfs函数那里，首先建立一个队列用于辅助BFS记录当前起始结点相邻结点，先记录起始结点的坐标（队列的元素类型是数组，每个数组记录两条信息：行、列），然后只要队列不空、队列元素值合法(不越界)、题目数组的对应位置元素值为1时，就将题目的数组该位置元素值置0，并将相邻结点坐标也加入队列，再循环判断队列是否为空......
当元素不合法时，元素坐标不会放入队列，队列元素会减少，直到为空，bfs函数的使命就是将符合的结点周围相连的1全部置0，以免重复算入岛屿数量。
因此只要一开始遍历数组，调用bfs函数并岛屿数量+1，遍历完后即可得出岛屿数量。
注意事项：以上出现了三个数组，一个是题目的数组，表示岛屿与海洋；一个是队列数组，说是数组其实是链表，当成数组用，存放起始和相邻结点；一个是队列的元素类型是数组，因为队列要记录的是结点的坐标，结点是二维数组的元素，所以要行+列，故而用一维数组类型int[]表示{i,j}。

二、DFS
也是上面那道题，不过不借助队列，直接抓到一个1就岛屿数量+1，然后顺着上下左右四个结点继续递归调用DFS,作用也是将抓到的1变0，并且继续抓上下左右的四个结点......直到范围超出或者为0。逻辑简单。

https://leetcode-cn.com/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/
jyd题解：
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}