[数据结构与算法]常见搜索问题

深度优先算法

题目：695 岛屿的最大数量
给了一个01组成的数组，1为岛屿，求其中最大岛屿的面积。

解题
使用DFS+沉岛法，把搜索过了的岛屿下沉

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        //特判
        if(grid.length==0||grid[0].length==0)return 0;
        //DFS+沉岛思想
        //主函数遍历从所有点作为起点时，对其相连的面积做判断，找出最大的一块连续区域
        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){
                    ans = Math.max(ans,dfs(grid,i,j));
                }
            }
        }
        return ans;

    }
    public int dfs(int[][] grid,int x,int y){
        //返回值为该块为起点的整个岛屿的大小
        //辅函数做递归，从主函数找到的第一块陆地开始，往其四周扩展，将这个岛屿的四周使用dfs的方式全部沉落
        //如果越界了，或者本身就是0，则返回0
        if(x<0||x>=grid.length||y<0||y>=grid[0].length||grid[x][y]==0)return 0;
        //否则说明该块为岛屿，下沉其和其周围的所有岛屿
        grid[x][y] = 0;
        int num = 1;
        num += dfs(grid,x-1,y);
        num += dfs(grid,x+1,y);
        num += dfs(grid,x,y-1);
        num += dfs(grid,x,y+1);
        return num;
    } 
}

剑指 Offer II 116. 朋友圈
题目：
给了一个数组，ij位置的元素表示i与j之间的关系，所有直接/间接认识的人组成了一个朋友圈，求一共有多少个朋友圈。

使用DFS+每个人是否加入朋友圈的一个一维数组实现

class Solution {
    public int findCircleNum(int[][] isConnected) {
        //特判
        if(isConnected.length==0||isConnected[0].length==0)return 0;
        //使用一个数组表示每一个元素是否有归属
        //使用DFS遍历所有元素，直至所有元素都有了自己的所属
        int cnt = 0;
        boolean used[] = new boolean[isConnected.length];
        for(int i =0;i<isConnected.length;i++){
            //遍历所有元素，如果它没有被遍历过，则从它开始找到所有属于它的圈子的
            if(used[i]==false){
                used[i] = true;
                dfs(used,isConnected,i);
                cnt++;
            }
            
        }
        return cnt;

    }

    public void dfs(boolean used[] ,int[][] isConnected,int x){
        for(int j = 0;j<isConnected[0].length;j++){
            if(isConnected[x][j]==1&&used[j]==false){
                used[j] = true;
                dfs(used,isConnected,j);
            }
        }
        return;
    }
}

广度优先算法