1 基本概念
1.1 图与连通性的定义
图论中的图由顶点和边组成，通常记为 \(G=(V,E)\)。其中，顶点表示对象，边表示对象之间的关系。在无向图中，如果两个顶点之间存在一条路径，便称它们是连通的。连通性描述的是图中顶点之间是否能够通过边相互到达，是研究图结构时最基础的性质之一。
在无向图里，连通关系具有自反性、对称性和传递性，因此可以把“能否通过路径相连”看作一种等价关系。正因为这一点，顶点集合往往可以按照连通关系自然地划分成若干部分。
1.2 连通分量的定义
连通分量是无向图中的一个连通子图，并且在包含更多顶点时就不再保持连通性。换言之，它是不能继续向外扩展的“最大连通部分”。图中的每个顶点都属于某一个连通分量，而一个图如果只有一个连通分量，就说明整张图是连通的。
1.2.1 极大连通子图
“极大”强调的是不能再加入其他顶点而仍保持连通。这里的“极大”不是指顶点数最多，而是指在当前图中已经无法继续扩大。若再加入任何一个不在其中的顶点，整体就会失去连通性，或者已经不满足子图的连通要求。
1.2.2 连通分量与连通图
若一张无向图本身就是连通的，那么它只有一个连通分量，且这个分量就是整张图。反之，如果图中存在多个互不连通的部分，那么每个部分都会形成独立的连通分量。于是，连通图可以看作“连通分量数量为 1”的特殊情形。
1.3 连通分量的直观理解
从直观上看，连通分量像是把一张图按“能走到一起”的标准切分成若干块。每一块内部任意两点都可通过路径相连，而不同块之间则没有路径贯通。
1.3.1 网络划分视角
如果把图看作网络，连通分量就相当于网络中的若干独立区域。区域内部信息可以自由传播，区域之间则没有直接通路。这样的划分方式常用于理解网络中哪些节点彼此可达，哪些节点处于不同“群组”。
1.3.2 孤立顶点与孤立子图
孤立顶点是指与任何其他顶点都没有边相连的顶点。它本身也可以看作一个连通分量，因为单个顶点天然满足连通性，只是这个分量只有一个顶点。类似地，若某个子图与图中其他部分完全断开，也会单独构成一个连通分量。
2 性质与判定
2.1 连通分量的基本性质
连通分量具有清晰的划分特征：每个顶点恰好属于一个分量，不同分量彼此不重叠，并且它们共同覆盖整张图的顶点集。这些性质使连通分量成为分析图结构时非常有用的基本单位。
2.1.1 唯一分解性
对于一张给定的无向图，其连通分量的划分是唯一的。也就是说，图一旦确定，分量的划分方式就随之唯一确定，不会因为不同的观察顺序而改变。这种唯一性保证了连通分量具有稳定的结构意义。
2.1.2 两两不相交性
不同连通分量之间没有共同顶点。若两个分量存在公共顶点，那么由该顶点出发可以把两者连接起来，它们就应合并为同一个连通分量。因此，连通分量之间必然是互不相交的。
2.1.3 顶点覆盖性
所有连通分量合起来能够覆盖图中全部顶点。即使某些顶点孤立无边，它们也不会被遗漏，而是各自形成单独的分量。因此，连通分量构成了顶点集合的一种完整划分。
2.2 连通分量的判定标准
判断某个子图是否是连通分量，关键要看两点：其内部是否连通，以及它是否已经无法继续扩展。前者保证“连成一块”，后者保证“已经足够大”。
2.2.1 顶点间可达关系
若一个顶点集合中的任意两点之间都存在路径，那么该集合对应的子图是连通的。进一步，如果图中不存在任何不属于该集合的顶点还能与其中顶点保持连通并将其扩展，那么它就满足连通分量的判定条件。
2.2.2 子图的极大性
极大性是判定连通分量的核心。一个连通子图如果还能加入图中的其他顶点并保持连通，它就不是连通分量；只有当它无法继续扩大时，才可称为连通分量。这个标准使连通分量区别于一般的连通子图。
2.3 特殊情形
连通分量在一些特殊图中表现得较为简单，便于直接判断。
2.3.1 单顶点分量
只有一个顶点的子图也算连通分量。它内部没有边，但“任意两点连通”在单点情形下是自然成立的，因此单顶点常作为最小的连通分量出现。
2.3.2 完全连通图中的连通分量
在完全连通图中，任意两个不同顶点之间都有边相连，因此整张图本身就是一个连通分量，不会再分裂成多个部分。这类图的连通结构最为简单，分量数量为 1。
2.3.3 含孤立点的图
若图中存在孤立点，那么这些顶点各自构成单独的连通分量。图中除孤立点之外的其他顶点，仍会按照自身的连通关系划分为若干分量。于是，这类图的分量数通常会比直观上的“成团部分”更多。
3 图中的相关概念
3.1 连通图
连通图是指图中任意两个顶点之间都存在路径。它是连通分量概念的基础：当整图连通时，图只有一个连通分量；当整图不连通时，则可被拆分为多个分量。
3.1.1 整图连通与分量数量
一张无向图是否连通，可以直接通过连通分量的个数判断。若分量数量为 1，则图连通；若大于 1，则图不连通。这个对应关系使“连通分量”成为检测整图连通性的常用工具。
3.2 弱连通与强连通
在有向图中，由于边具有方向，连通性的定义需要更细化。此时常区分弱连通和强连通两个层面。
3.2.1 有向图中的弱连通分量
弱连通分量是把有向图中的边忽略方向后，得到的无向图中的连通分量。它关注的是顶点之间“是否能通过某种边链条联系起来”，而不强调方向是否一致。
3.2.2 有向图中的强连通分量
强连通分量要求在有向图中，分量内任意两点都能沿有向路径相互到达。它比弱连通分量更严格，因此一个弱连通分量内部，可能包含多个强连通分量。
3.3 割点与桥
割点和桥与连通分量的变化关系密切，是研究图结构脆弱性的常见概念。
3.3.1 去除顶点后的分量变化
若删除某个顶点后，图的连通分量数量增多，则该顶点可能是割点。割点的存在说明图在该处存在“关键节点”，移除后会使原本连通的部分被拆开。
3.3.2 去除边后的分量变化
若删除某条边后，图的连通分量数量增加，则该边是桥。桥表示这条边是连接两个部分的唯一通道，一旦移除，图就会被分裂。
3.4 块与连通分量的区别
块是比连通分量更细的结构单位，常用于进一步分析图的内部组织。
3.4.1 二连通分量
二连通分量通常指在删除任意一个顶点后仍保持连通的最大子图。它比普通连通分量更强调内部的稳固性，因此与割点的讨论关系紧密。
3.4.2 点连通性与边连通性
点连通性关注删除顶点对图连通性的影响，边连通性则关注删除边后的变化。连通分量是这两类概念的基础背景，而块、割点、桥等概念则是在此基础上进一步细分出的结构性质。
4 求解方法与算法
4.1 深度优先搜索
深度优先搜索是一种常用的连通分量求解方法。它从某个未访问顶点出发，沿着边尽可能深入访问相邻顶点，直到无法继续，再回溯到其他分支。对无向图进行多次 DFS，可以依次找出所有连通分量。
4.1.1 基于 DFS 的分量标记
实现时，通常维护一个访问数组。每当遇到一个未访问顶点，就以它为起点启动 DFS，并把在本次搜索中访问到的所有顶点标记为同一个分量编号。重复这一过程，直到所有顶点都被访问完毕。
4.1.2 时间复杂度分析
在邻接表表示下，DFS 遍历整张图的时间复杂度通常为 \(O(V+E)\)，其中 \(V\) 是顶点数，\(E\) 是边数。每个顶点和每条边一般只会被处理常数次，因此效率较高。
4.2 广度优先搜索
广度优先搜索同样可以用于求连通分量。它从起点出发，按层次逐步扩展，先访问与起点距离较近的顶点，再访问更远的顶点。
4.2.1 基于 BFS 的分量遍历
与 DFS 类似，BFS 也可以把从同一起点出发能访问到的所有顶点划入同一分量。区别在于，BFS 采用“先入先出”的扩展方式，因此访问顺序更偏向层次化。
4.2.2 队列实现与分量划分
BFS 通常借助队列实现。起始顶点入队后，循环取出队首顶点并访问其邻接点，将未访问的邻点继续入队。一个分量遍历结束后，再寻找下一个未访问顶点作为新的起点，即可完成整图分量划分。
4.3 并查集
并查集适合处理动态连通性问题。它通过“合并集合”和“查询所属集合”的操作，快速维护图中顶点之间的连通关系。
4.3.1 动态维护连通性
当边不断加入图中时，可以用并查集合并边两端顶点所在的集合。若两点最终落在同一集合中，就说明它们连通。对于需要频繁插入边并查询连通关系的场景，并查集非常方便。
4.3.2 适用场景与局限
并查集更适合边的动态增加，而不擅长处理频繁删除边或删除顶点的情况。因为删除操作会破坏原有集合结构，通常需要额外维护，复杂度也会显著上升。
4.4 算法比较
不同算法在适用场景和实现方式上各有特点。
4.4.1 静态图与动态图
对于静态图，DFS 和 BFS 都能直接求出连通分量，写法简洁且效率稳定。对于动态图，尤其是边不断加入的情形，并查集更有优势；若还涉及删除操作，则问题会更复杂，通常需要更专门的数据结构。
4.4.2 递归实现与非递归实现
DFS 常见递归写法，代码简洁，但在大规模图中可能受到递归深度限制。非递归 DFS 或 BFS 则通过显式栈、队列来实现，通常更适合工程化场景，也更便于控制内存使用。
5 表示与例子
5.1 邻接矩阵中的分量识别
在邻接矩阵表示下，判断连通分量时，需要检查某顶点是否与其他顶点相邻。虽然矩阵查询方便，但遍历时往往要扫描整行，时间开销相对较大。若图较稠密，这种表示法仍然比较直观。
5.2 邻接表中的分量识别
邻接表更适合稀疏图。每个顶点只保存自己的邻接顶点列表，因此在 DFS 或 BFS 中可以直接遍历相关边，效率通常更高。连通分量求解中，邻接表也是最常用的存储方式之一。
5.3 典型示例图
通过具体图例，可以更直观地理解连通分量的划分方式。
5.3.1 含多个分量的无向图
若一张无向图中存在两组顶点，它们内部各自连通，但组与组之间没有任何边相连，那么这两组就分别形成两个连通分量。这类例子最能体现“最大连通子图”的含义。
5.3.2 含环与树状结构的混合图
有些连通分量内部既包含环，也包含树状分支。只要这些顶点彼此整体连通，它们仍然属于同一个分量。是否存在环，不影响连通分量的定义，只影响更细的结构性质。
5.3.3 孤立顶点示例
在只有少量边的图中，某些顶点可能完全没有与其他顶点相连。此时，每个孤立点都会单独成为一个分量，常被用于说明“单点也能构成连通分量”。
5.4 分量标号与可视化
实际处理中，常给每个连通分量编号。顶点被访问时记录所属编号，最后便可得到每个分量的顶点集合。可视化时，常用不同颜色或边框把不同分量区分开来，使图的结构层次更加清晰。
6 应用
6.1 网络分析
连通分量在网络分析中非常常见，可用于识别网络是否整体连通，以及网络中是否存在相互独立的区域。
6.1.1 社交网络中的群组划分
在社交网络模型中，连通分量可以表示彼此有联系的一组用户。虽然现实中的社交关系更复杂，但连通分量提供了一种基础的群组划分方法，便于观察网络中的聚集现象。
6.1.2 通信网络中的可达性分析
在通信系统中，连通分量可以帮助判断哪些设备之间存在通信路径，哪些设备处于孤立状态。若某些节点属于不同分量，则说明它们之间当前无法直接或间接通信。
6.2 计算机科学中的应用
在计算机科学中，连通分量常作为图算法的基础环节，广泛出现于图像处理、程序分析和数据结构设计中。
6.2.1 图像处理中的区域分割
把图像中的像素或像素块抽象为图后，连通分量可以用于提取连通区域。常见于目标轮廓识别、前景分割等任务，尤其适合处理由相邻像素构成的区域结构。
6.2.2 程序依赖分析
在程序依赖图或调用关系图中，连通分量有助于识别相互关联的代码模块。通过分析分量，可以了解程序结构是否分散，以及某些模块是否彼此独立。
6.3 数学建模中的应用
在数学建模里，连通分量常用来描述系统内部的模块划分与耦合关系。
6.3.1 系统分块与模块化
复杂系统往往可以拆分成若干相对独立的子系统。连通分量提供了一种自然的分块方式，使整体问题转化为多个局部问题，便于分析和求解。
6.3.2 结构稳定性分析
在结构模型中，如果一个系统的关键连接被破坏，连通分量会随之变化。通过观察分量是否分裂，可以评估系统的稳定程度以及哪些连接点更为重要。
7 常见题型与练习
7.1 连通分量数量计算
这类题目通常给出一张图，要求判断共有多少个连通分量。解题时可先从未访问顶点出发进行一次遍历，并把访问到的点全部标记为同一分量，直到所有顶点处理完毕。
7.2 分量顶点集合求解
除了数量之外，有些题目还要求写出每个分量包含哪些顶点。此时需要在搜索过程中记录分量成员，最后按编号输出。此类题目很适合检验对 DFS、BFS 的掌握程度。
7.3 删除边或点后的分量变化
这类问题会考查某条边或某个顶点被删除后，图的连通结构如何变化。通常需要结合桥和割点的概念判断，也可能要求重新分析删除后的连通分量数量。
7.4 算法实现题
算法实现题常要求用代码求出连通分量，或在动态输入下维护连通性。
7.4.1 DFS 代码题
这类题目一般要求用深度优先搜索遍历图，并输出分量个数、分量编号或分量成员。重点在于正确处理访问标记，避免重复遍历。
7.4.2 BFS 代码题
BFS 题目通常要求使用队列完成分量划分。与 DFS 相比，BFS 的思路更偏向逐层扩展，但结果一致，都是把同一连通区域中的顶点归为一类。
7.4.3 并查集应用题
并查集题目常见于“边逐步加入”“判断两点是否连通”等场景。解题关键在于熟练使用合并与查询操作，并理解其适合静态维护或增量维护连通性的特点。