在开发马尔可夫分析模型功能的过程中，遇到了一个计算前检验模型是否合格的问题。其中最主要的就是要检验图中是否存在单独的节点，即多个连通分量。
什么是连通分量？
通俗地讲，在无向图中，若所有节点都是连通的（即任意选定两个节点，都存在至少一条路使得两个节点连通），则该图有且仅有一个连通子图，即它本身。此时称该图的连通分量为1。这便是马尔可夫过程模型需要检验的条件。
上图存在了单独的节点
上图连通分量大于1
深度优先搜索的思路是最直观的。遍历图中所有节点，对于每个节点，如果该节点尚未被访问过，则从该节点开始深度优先搜索，通过邻接矩阵
isConnected
得到与该节点直接相连的节点有哪些，这些节点和该节点属于同一个连通分量，然后对这些节点继续深度优先搜索，直到同一个连通分量的所有节点都被访问到，即可得到一个节点。遍历全部节点以后，即可得到连通分量的总数。
* DFS深度优先遍历计算连通分量数
* @param isConnected : 邻接矩阵 (二维数组)
* @returns circles:连通分量数
* nodeNum:节点数量 visited:已访问节点集
var
findCircleNum
=
function
(
isConnected
)
{
const
nodeNum
=
isConnected
.
length
;
const
visited
=
new
Set
(
)
;
let
circles
=
0
;
for
(
let
i
=
0
;
i
<
nodeNum
;
i
++
)
{
if
(
!
visited
.
has
(
i
)
)
{
dfs
(
isConnected
,
visited
,
nodeNum
,
i
)
;
circles
++
;
return
circles
;
const
dfs
=
(
isConnected
,
visited
,
nodeNum
,
i
)
=>
{
for
(
let
j
=
0
;
j
<
nodeNum
;
j
++
)
{
if
(
isConnected
[
i
]
[
j
]
==
1
&&
!
visited
.
has
(
j
)
)
{
visited
.
add
(
j
)
;
dfs
(
isConnected
,
visited
,
nodeNum
,
j
)
;
也可以通过广度优先搜索的方法得到连通分量的总数。对于每个节点，如果该节点尚未被访问过，则从该节点开始广度优先搜索，直到同一个连通分量中的所有节点都被访问到，即可得到一个连通分量。
* BFS广度优先遍历计算连通分量数
* @param isConnected : 邻接矩阵 (二维数组)
* @returns circles:连通分量数
* nodeNum:节点数量 visited:已访问节点集
var
findCircleNum
=
function
(
isConnected
)
{
const
nodeNum
=
isConnected
.
length
;
const
visited
=
new
Set
(
)
;
let
circles
=
0
;
const
queue
=
new
Array
(
)
;
for
(
let
i
=
0
;
i
<
nodeNum
;
i
++
)
{
if
(
!
visited
.
has
(
i
)
)
{
queue
.
push
(
i
)
;
while
(
queue
.
length
)
{
const
j
=
queue
.
shift
(
)
;
visited
.
add
(
j
)
;
for
(
let
k
=
0
;
k
<
nodeNum
;
k
++
)
{
if
(
isConnected
[
j
]
[
k
]
===
1
&&
!
visited
.
has
(
k
)
)
{
queue
.
push
(
k
)
;
circles
++
;
return
circles
;
计算连通分量数的另一个方法是使用并查集。初始时，每个节点都属于不同的连通分量。遍历矩阵
isConnected
，如果两个节点之间有相连关系，则它们属于同一个连通分量，对它们进行合并。
遍历矩阵
isConnected
的全部元素之后，计算连通分量的总数。
* 并查集 计算连通分量数
* @param isConnected
* @returns circles:连通分量数
* nodeNum:节点数量 visited:已访问节点集
var
findCircleNum
=
function
(
isConnected
)
{
const
nodeNum
=
isConnected
.
length
;
const
parent
=
new
Array
(
nodeNum
)
.
fill
(
0
)
.
map
(
(
element
,
index
)
=>
index
)
;
for
(
let
i
=
0
;
i
<
nodeNum
;
i
++
)
{
for
(
let
j
=
i
+
1
;
j
<
nodeNum
;
j
++
)
{
if
(
isConnected
[
i
]
[
j
]
==
1
)
{
union
(
parent
,
i
,
j
)
;
let
circles
=
0
;
parent
.
forEach
(
(
element
,
index
)
=>
{
if
(
element
===
index
)
{
circles
++
;
}
)
;
return
circles
;
const
union
=
(
parent
,
index1
,
index2
)
=>
{
parent
[
find
(
parent
,
index1
)
]
=
find
(
parent
,
index2
)
;
const
find
=
(
parent
,
index
)
=>
{
if
(
parent
[
index
]
!==
index
)
{
parent
[
index
]
=
find
(
parent
,
parent
[
index
]
)
;
return
parent
[
index
]
;
|
方法
|
时间复杂度
|
空间复杂度
|
|
深度优先DFS
|
O(n
2
)
|
O(n)
|
|
广度优先BFS
|
O(n
2
)
|
O(n)
|
|
并查集
|
O(n
2
logn)
|
O(n)
|
|
其中，n是节点数量。对于DFS和BFS，时间上都需要遍历邻接矩阵内的所有元素，即n
2
，空间上都需要一个长度为n的数组来标记已经访问过的节点。
|
|
|
|
对于并查集，时间上除了遍历邻接矩阵内的所有元素外，若存在相连关系，最多可能有2n
2
次查找，和log(n
2
)次合并。故最坏的情况下复杂度为O(2n
2
log(n
2
)) = O(n
2
logn)，空间上需要一个长度为n的数组来记录每个节点的祖先。
|
|
|
参考资料：
链接：https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/
来源：力扣（LeetCode）
LeetCode.200 岛屿数量 【高频考题】
LeetCode.323 无向图中连通分量的数目
LeetCode.694 不同岛屿的数量
LeetCode.305 岛屿数量 II
LeetCode.286 墙与门
LeetCode.542 01 矩阵
LeetCode.994 腐烂的橘子
【JavaScript算法实践】无向图连通分量问题无向图连通分量不符合条件的情况连通分量计算方法一：深度优先搜索（DFS）方法二：广度优先搜索（BFS）方法三：并查集复杂度分析无向图连通分量在开发马尔可夫分析模型功能的过程中，遇到了一个计算前检验模型是否合格的问题。其中最主要的就是要检验图中是否存在单独的节点，即多个连通分量。什么是连通分量？通俗地讲，在无向图中，若所有节点都是连通的（即任意选定两个节点，都存在至少一条路使得两个节点连通），则该图有且仅有一个连通子图，即它本身。此时称该图的连通分量为
1065:
无向图
的
连通分量
计算
1.利用图的
深度优先
搜索
（DFS）：从图中的某个顶点出发，访问此顶点，然后从v的未被访问的邻接点出发
深度优先
遍历图，若图中有顶点未被访问，则另选一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。若是连通图则只会执行一次，所以利用DFS对图进行
搜索
，对只执行一次的连通图进行计数，即为
无向图
中
连通分量
的个数。
假设
无向图
G采用邻接矩阵存储，编写一个
算法
求
连通分量
的个数。
第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1
问题
描述
已知
无向图
的顶点为字符型，要求采用邻接矩阵表示，图中顶点序号按字符顺序排列，从键盘输入图中顶点的个数、边的条数、顶点的信息和边的组成等。(注意：判断一个
无向图
是否连通) 求一个
无向图
的
连通分量
。
第一行输入
无向图
的顶点数和边的条数，以空格隔开
第二行输入每个顶点的数据，中间没有空格
第三行输入每条边，每条边的格式为i j，中间有空格，所有边占一行
输出该
无向图
的连通...
文章目录
无向图
双
连通分量
1.基本术语与概念1.1.割点1.2.桥1.3.边双
连通分量
(e-DCC)1.4 点双
连通分量
(v-DCC)1.5 时间戳2.求解2.1 边双
连通分量
2.1.1 如何找到桥？2.1.2 如何找所有边的双
连通分量
？2.1.3 例题 acwing 395. 冗余路径参考资料
无向图
双
连通分量
1.基本术语与概念
给定一个
无向图
G = (V,E):
1.1.割点
1.2.桥
1.3.边双
连通分量
(e-DCC)
极大的不含有桥的连通块被称为边双
连通分量
。
图中的两个边双连
