leeteCode|547. 省份数量 BFS|连通分量|算法

题目描述：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中省份的数量。

题目示例1：

【leeteCode|547. 省份数量】输入：isConnected = [ [1,1,0],[1,1,0],[0,0,1]]
输出：2

题目示例2：

输入：isConnected = [ [1,0,0],[0,1,0],[0,0,1]]
输出：3

题目示例3：

输入：isConnected = [ [1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]
输出：1

这道题我们先不说考察什么，我们先看看题目想表达什么意思？
我们以示例3为例进行讲解
示例3构成的矩阵如下所示：

文章图片

其中a,b,c,d代表四个城市
先看第一行：

a到b无法连通
a到c无法连通
a到d可以连通

此时可以组成：

文章图片

接下来我们来到d所在的一行即第四行

d到a可以连通
d到b无法连通
d到c可以连通

此时可以组成：

此时的结点有a,d,c。因为a,d我们都访问过了，在看c这一行

c到a无法连通
c到b可以连通
c到d可以连通

于是我们可以得到以下组成：

此时我们可以看到四个城市全部可以连通，于是省会只有一个
以上过程就是找无向图连通分量的过程
我们接下来看看BFS（广度优先搜索）是如何实现的

import java.util.LinkedList; import java.util.Queue; public class 省份数量_547 { public int findCircleNum(int[][] isConnected) { int provinces = isConnected.length; boolean[] visited = new boolean[provinces]; int circles = 0; Queue queue = new LinkedList(); 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; }public static void main(String[] args) { 省份数量_547 test = new 省份数量_547(); int[][] isConnected = {{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}}; System.out.println(test.findCircleNum(isConnected)); } }