java数据结构与算法刷题-----LeetCode547. 省份数量

本文主要是介绍java数据结构与算法刷题-----LeetCode547. 省份数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

文章目录

- 深度优先遍历
- 广度优先遍历

本题考察图的连通分量个数。也就是所有直接或间接通过边相连的顶点构成一个连通分量，一个无向图有1到多个连通分量组成

`深度优先遍历`

解题思路：时间复杂度O( $n^2$ ),需要遍历每一条边，空间复杂度O( $n$ )，需要一个数组标识n个顶点是否访问过

这是一个由领接矩阵表示的图，特点是用一个二维数组arr[i][j]表示顶点之间的关系。i表示顶点，j表示i这个顶点与谁有边。例如arr[0][3]，就是是说0这个顶点和3这个顶点有一条边，他俩是连通的
我们依次访问每个顶点，并遍历其边的信息，如果有边，就遍历这条边相连的顶点B，然后再次遍历B的边，依次类推

代码

class Solution {public int findCircleNum(int[][] isConnected) {int count=0;//最终答案int L = isConnected.length;//顶点个数boolean[] visit=new boolean[L];//顶点是否访问for(int i=0;i<L;++i)//遍历每个顶点{if(!visit[i])//如果没有访问过{dfs(isConnected,i,visit);//访问其连通分量count+=1;//连通分量数量+1}}return count;//连通分量的个数}public void dfs(int[][] isConnected,int i,boolean[] visit)//深度遍历其连通分量{visit[i]=true;//设置当前顶点为访问过的状态for(int k=0;k<isConnected.length;++k)//遍历其边{    //如果当前边相连顶点没有访问过，并且当前边存在的话，就遍历这个顶点if(visit[k]==false && isConnected[i][k]==1)dfs(isConnected,k,visit);}}}

`广度优先遍历`

解题思路：时间复杂度O( $n^2$ )，空间复杂度O( $n$ )

将深度优先遍历的代码换成广度优先即可

代码

class Solution {public int findCircleNum(int[][] isConnected) {int cities = isConnected.length;//顶点个数boolean[] visited = new boolean[cities];//是否访问int provinces = 0;//连通分量个数Queue<Integer> queue = new LinkedList<Integer>();//队列，用于广度优先遍历for (int i = 0; i < cities; i++) {if (!visited[i]) {//如果当前顶点没有访问queue.offer(i);//对其广度优先遍历while (!queue.isEmpty()) {int j = queue.poll();//出队列visited[j] = true;//标为访问过for (int k = 0; k < cities; k++) {//遍历其边if (isConnected[j][k] == 1 && !visited[k]) {//如果边存在且顶点没有访问过queue.offer(k);//就入队列，下次继续广度优先遍历}}}provinces++;//遍历完成一个连通分量}}return provinces;}
}