算法基础——广度优先搜索 / 深度优先搜索（一）

一、岛屿数量

• 深度优先搜索
  • 当找到岛的边界，就用深度搜索将这整个岛“沉”了——将元素“1”本身及其四个正方向赋值为“0”

class Solution {
    public int numIslands(char[][] grid) {
        int ans = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    //沉岛
                    chengdao(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void chengdao(char[][] grid, int i, int j){
        if(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == '1') {
            grid[i][j] = '0';
            chengdao(grid, i - 1, j);
            chengdao(grid, i + 1, j);
            chengdao(grid, i, j - 1);
            chengdao(grid, i, j + 1);
        }
    }
}

• 广度优先搜索
  • 同样是找到岛边界后，统计岛的数量，然后沉岛
  • 沉岛：使用队列保存岛各个坐标，然后取出将元素赋值为“0”，再将其四个正方向的坐标（必须值为“1”）记录到队列中

二、省份数量

• 广度优先搜索

  • isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连：

    • isConnected[i][i] == 1：说明对角线是一个城市，那么至少有isConnected.length个省

    • 当isConnected[i][j] = 1时，第i行的城市都属于同一个省

    • 利用这个进行搜索，当i行中有第j个元素等于1的情况，那么j这一行同属一个省

      • 那么，探寻数组中记录j被访问

    • 利用一个探询数组，记录被记录到省内的信息

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    for (int k = 0; k < provinces; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                circles++;
            }
        }
        return circles;
    }
}

• 深度优先搜索
  • 搜索方式改变，但细节处理不变