0323. 无向图中连通分量的数目 #
- 标签:深度优先搜索、广度优先搜索、并查集、图
- 难度:中等
题目大意 #
描述:给定 n
个节点(编号从 0
到 n - 1
)的图的无向边列表 edges
,其中 edges[i] = [u, v]
表示节点 u
和节点 v
之间有一条无向边。
要求:计算该无向图中连通分量的数量。
说明:
- $1 \le n \le 2000$。
- $1 \le edges.length \le 5000$。
- $edges[i].length == 2$。
- $0 \le ai \le bi < n$。
- $ai != bi$。
edges
中不会出现重复的边。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
先来看一下图论中相关的名次解释。
- 连通图:在无向图中,如果可以从顶点 $v_i$ 到达 $v_j$,则称 $v_i$ 和 $v_j$ 连通。如果图中任意两个顶点之间都连通,则称该图为连通图。
- 无向图的连通分量:如果该图为连通图,则连通分量为本身;否则将无向图中的极大连通子图称为连通分量,每个连通分量都是一个连通图。
- 无向图的连通分量个数:无向图的极大连通子图的个数。
接下来我们来解决这道题。
思路 1:深度优先搜索 #
- 使用
visited
数组标记遍历过的节点,使用count
记录连通分量数量。 - 从未遍历过的节点
u
出发,连通分量数量加 1。然后遍历与u
节点构成无向边,且为遍历过的的节点v
。 - 再从
v
出发继续深度遍历。 - 直到遍历完与
u
直接相关、间接相关的节点之后,再遍历另一个未遍历过的节点,继续上述操作。 - 最后输出连通分量数目。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中$n$ 是顶点个数。
- 空间复杂度:$O(n)$。
思路 2:广度优先搜索 #
- 使用变量
count
记录连通分量个数。使用集合变量visited
记录访问过的节点,使用邻接表graph
记录图结构。 - 从
0
开始,依次遍历n
个节点。 - 如果第
i
个节点未访问过:- 将其添加到
visited
中。 - 并且连通分量个数累加,即
count += 1
。 - 定义一个队列
queue
,将第i
个节点加入到队列中。 - 从队列中取出第一个节点,遍历与其链接的节点,并将未遍历过的节点加入到队列
queue
和visited
中。 - 直到队列为空,则继续向后遍历。
- 将其添加到
- 最后输出连通分量数目
count
。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。其中$n$ 是顶点个数。
- 空间复杂度:$O(n)$。