1. 概述
在本教程中，我们将讨论图（Graph）中 连通分量（Connected Components） 的概念。
我们会通过几个简单示例帮助理解其基本含义，并列出连通分量的一些关键性质。同时，我们还会介绍如何通过 DFS 算法来找出图中连通分量的数量，并进行时间复杂度分析。
2. 连通分量定义
在一个 无向图（Undirected Graph） 中，连通分量（Connected Component）是指一个 子图（Subgraph），其中任意两个节点之间都存在路径（Path）可以相互到达。
换句话说：
一组节点构成一个连通分量，当且仅当其中任意两个节点之间都可达。
关键点在于“可达性”。在一个连通分量内部，所有节点都是互相连通的。
3. 示例说明
我们来看几个简单的例子，帮助理解连通分量的定义。
3.1. 单个连通分量
下面这个无向图只有一个连通分量：
设该图记为 G1(V, E)，其中：
- 顶点集合 V = {V1, V2, V3, V4, V5, V6}
- 边集合 E = {E1, E2, E3, E4, E5, E6, E7}
G1 包含一个连通分量 C1，它包含了图中所有顶点。我们随便选两个顶点 V1 和 V6：
- V6 可以通过路径 E4 → E7 或 E3 → E5 → E7 到达 V1
- V1 也可以通过反向路径回到 V6
这说明 C1 中任意两个节点都能相互到达，符合连通分量的定义。
3.2. 多个连通分量
下面这个图包含三个连通分量：
设该图记为 G2(V, E)，其中：
- V = {V1, V2, V3, V4, V5, V6, V7, V8, V9, V10, V11, V12}
- E = {E1, E2, ..., E11}
三个连通分量分别为：
- C1 = {V1, V2, V3, V4, V5, V6}
- C2 = {V7, V8, V9}
- C3 = {V10, V11, V12}
我们分别从这三个集合中各选两个节点进行可达性验证：
- C1 中 V4 和 V6 可达
- C2 中 V8 和 V9 可达
- C3 中 V11 和 V12 可达
说明这三个集合都满足连通分量的定义。
4. 连通分量的性质
连通分量具有以下几个重要性质：
✅ 非空性：每个连通分量集合都非空。
✅ 并集等于全集：若图中存在多个连通分量，则它们的并集等于图中所有顶点的集合。
例如图 G2 中：
$$ C1 \cup C2 \cup C3 = V $$
✅ 互不相交：任意两个不同的连通分量之间没有交集（即它们是 两两不交（Pairwise Disjoint） 的）。
例如图 G2 中：
$$ C1 \cap C2 \cap C3 = \emptyset $$
5. 连通分量的查找算法
给定一个无向图，找出其连通分量的数量是图结构分析中的一个基础任务，具有广泛的实际应用。
我们可以使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 来实现。
下面是基于 DFS 的算法实现（Java 伪代码）：
algorithm FindConnectedComponents(G):
// G: 无向图，包含顶点 V 和边 E
// 输出：连通分量的数量
Component_Count ← 0
Visited ← 空映射（记录顶点是否已访问）
for 每个顶点 k in V:
Visited[k] ← false
for 每个顶点 k in V:
if 未访问:
DFS(V, k)
Component_Count ← Component_Count + 1
print Component_Count
algorithm DFS(V, k):
// V: 图中所有顶点
// k: 当前探索的顶点
// 功能：从顶点 k 开始执行深度优先搜索，标记所有可达顶点为已访问
Visited[k] ← true
for 每个顶点 p in Adj[k]: // Adj[k] 是顶点 k 的邻接点
if 未访问 p:
DFS(V, p)
关键点：
- Component_Count 记录了调用 DFS 的次数，即连通分量的数量。
- DFS 会递归标记所有与当前顶点相连的节点为“已访问”。
- 所有未访问的顶点都会触发一次新的 DFS 调用。
6. 算法测试示例
我们以一个具体的图 G3(V, E) 来演示算法的执行过程：
其中：
- V = {V1, V2, V3, V4, V5, V6, V7, V8}
- E = {E1, E2, E3, E4, E5}
我们按顺序执行以下步骤：
- 初始化所有顶点为未访问（红色）
- 从 V1 开始 DFS，标记 V1、V2、V3 为已访问（绿色）
- 从 V4 开始 DFS，标记 V4、V5
- 从 V6 开始 DFS，标记 V6、V7
- 从 V8 开始 DFS，标记 V8
最终 Component_Count = 4，说明图中有 4 个连通分量：
- C1 = {V1, V2, V3}
- C2 = {V4, V5}
- C3 = {V6, V7}
- C4 = {V8}
如下图所示：
7. 时间复杂度分析
使用邻接表（Adjacency List）
- DFS 遍历所有顶点一次：O(V)
- 每条边访问两次（无向图）：O(E)
- 总时间复杂度：✅ O(V + E)
使用邻接矩阵（Adjacency Matrix）
- 每个顶点都要遍历整行查找邻接点：O(V²)
- 总时间复杂度：✅ O(V²)
8. 总结
本文我们讲解了图中 连通分量 的定义和性质，并通过两个简单示例帮助理解。
我们还介绍了一个基于 DFS 的算法来找出图中连通分量的数量，并进行了算法执行过程的演示和时间复杂度分析。
这类问题在社交网络分析、网络拓扑检测、图像分割等实际场景中都有广泛应用。掌握连通分量的查找方法，是理解图结构和构建图算法的基础技能之一。