[数据结构与算法]省份数量问题【深度优先遍历 广度优先遍历】

使用了递归之后，时间复杂度都会变为O(n)或者O(logN)

1、深度优先

public static void main(String[] args) {
        //这个表示下标为0的城市连了自己和1号城市，没有连2号城市。
        //1号城市连了0和自己。2号城市只连了自己，所以这里省份为2.
        System.out.println(getProvince(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
        //System.out.println(getProvince(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
    }

    //深度遍历
    public static int getProvince(int[][] cityiesConnected){
        int cities = cityiesConnected.length; //获取城市个数
        boolean[] visited=new boolean[cities];//标志位 标志过了的就不用遍历
        int provinces=0; //计数器
        //这里i=0表示第0个城市{1,1,0}
        for (int i = 0; i < cities; i++) {
            //如果还没被遍历过就使用深度遍历来遍历他
            if (!visited[i]){
                //深度遍历 如第0个城市：{1,1,0} 看他有多少个1表示相连的
                dfs(i,cities,visited,cityiesConnected);
                provinces++;
            }
        }
        return provinces;
    }

    private static void dfs(int i, int cities, boolean[] visited, int[][] cityiesConnected) {
        for (int j = 0; j < cities; j++) {
            if (cityiesConnected[i][j]==1 && !visited[j]){
                visited[j]=true; //如果为1就标志它
                //如果找到其中的一个城市的话，继续dfs遍历
                dfs(j,cities,visited,cityiesConnected);
            }
        }
    }

这个递归还是有点不太懂，还是调试好懂一些。这里的精髓在与你找到城市就在此城市继续dfs，标志，然后是你如果都标志的话，那么只会走一次proinces++而已，这就是为什么可以统计。

2、广度优先

待补充…

3、并查集

待补充…