1 基本概念
连通图是图论中最基础的研究对象之一，用来描述图中顶点之间的可达关系。对于无向图而言，若任意两个顶点之间都能通过若干边连接成一条路径，则称该图连通。若存在至少一对顶点彼此不可达，则该图为非连通图。
1.1 图与路径
图由顶点和边组成，路径则是连接顶点的一种行走方式。连通性的讨论通常以路径是否存在为核心，因此理解图与路径的基本定义，是把握连通图概念的前提。
1.1.1 顶点、边与邻接关系
顶点是图中的基本节点，边用于表示顶点之间的联系。在无向图中，若两个顶点之间由一条边直接相连，则称它们彼此邻接。邻接关系决定了图的局部结构，也影响全局的可达性。
1.1.2 路径、简单路径与回路
路径是由若干条边首尾相接形成的顶点序列，其中相邻顶点必须通过边连接。若路径中顶点不重复，通常称为简单路径。若路径的起点与终点相同，则构成回路，也称闭路径。连通性的判断往往建立在路径存在与否之上。
1.2 连通图的定义
连通图强调图内任意两点之间都可以互相到达。这个定义适用于无向图，是图论中最常见、也最直观的连通性表述。
1.2.1 无向图中的连通性
在无向图中，如果从任意顶点出发，都能沿着边走到其他任意顶点，那么该图就是连通图。也就是说，图中的顶点集合在路径意义下形成一个整体，而不是彼此分散成多个部分。
1.2.2 连通与非连通的判定
判定一个无向图是否连通，通常只需检验是否存在从某一顶点可达全部顶点的路径集合。若遍历过程中所有顶点都能被访问到，则图连通；若有顶点无法到达，则图非连通。该判定是后续算法设计的基础。
1.3 相关术语
连通图研究中常伴随若干重要术语，它们用于刻画图的分块结构以及局部连通特征。
1.3.1 连通分量
连通分量是非连通图中彼此连通的最大顶点子集。每个连通分量内部任意两点都可达，而不同分量之间没有路径相连。连通分量的划分能够清晰反映图的整体结构。
1.3.2 极大连通子图
极大连通子图指的是在图中不能再加入更多顶点而仍保持连通的子图。它与连通分量本质上对应，是描述图分解方式的重要概念。对于连通图本身，其整体也可视为一个极大连通子图。
2 连通图的性质
连通图具有一系列稳定而直观的性质，这些性质既反映了图的整体结构，也为算法分析提供了理论依据。
2.1 基本性质
连通图最核心的特征是任意两点之间的可达性，这一性质决定了图在路径层面上的整体统一性。
2.1.1 任意两点可达性
连通图中任意选取两个顶点，都存在一条路径将它们连接起来。这个性质意味着图中的信息、关系或流动可以在全图范围内传播，不会被局部结构完全阻断。
2.1.2 连通性与子图关系
一个连通图的子图未必连通，因为删除某些顶点或边后，原本可达的路径可能被切断。相反，连通图也可能包含多个连通的局部结构，但只要整体上任意两点都可达，图仍然保持连通。
2.2 极端情况
在研究连通图时，一些边界情形有助于加深对定义的理解。
2.2.1 单顶点图
只有一个顶点且没有边的图，通常被视为连通图。因为“任意两个顶点之间存在路径”在此情形下没有需要额外连接的不同顶点，故该定义自然成立。
2.2.2 空图与孤立点
空图通常指没有边的图。若图中有多个顶点且完全没有边，则各顶点彼此不可达，因而非连通。若某个顶点没有任何相邻边，则称为孤立点，它往往是图非连通的直接表现之一。
2.3 结构性质
连通图不仅在定义上有明确标准，在边数和结构形态上也存在一些常见约束。
2.3.1 最少边数条件
对于含有 n 个顶点的连通无向图，至少需要 n−1 条边。若边数少于这个数，图不可能连通。这个下界说明，连通性至少要求图中具有足够的连接骨架。
2.3.2 树与连通图的关系
树是一类特殊的连通图，它在保持连通的同时不含回路。换言之，树是“最简”的连通结构之一；去掉任何一条边都可能破坏连通性，这使它在结构上具有高度紧凑的特征。
3 特殊类型的连通图
某些图类在连通性方面具有特别清晰的表现，因而常被单独讨论。
3.1 完全图
完全图指任意两个不同顶点之间都存在一条边的图。它在连通性上具有最强的直接性。
3.1.1 完全图的连通性
完全图必然是连通图，因为任意两点之间不仅存在路径，而且可以直接相连。无论顶点数量多少，只要边按完全图规则构造，连通性都自动成立。
3.1.2 完全图的路径特征
在完全图中，最短路径长度通常非常小，任意两个不同顶点之间只需一步即可到达。因此，它是研究路径长度下界和网络高密度结构时的典型模型。
3.2 树
树是图论中最经典的连通无环结构，在很多算法与理论命题中都扮演基础角色。
3.2.1 树的定义
树通常定义为一个连通且不含回路的无向图。也可等价地理解为：任意两个顶点之间存在唯一一条简单路径。这个定义突出了树在连通性与路径唯一性上的双重特征。
3.2.2 树的连通性与无环性
树之所以重要，在于它把连通与无环结合在一起。连通保证图整体不分裂，无环则避免冗余连接。正因如此，树常被视为连通结构的基础骨架。
3.3 二分图中的连通性
二分图将顶点划分为两个互不相交的集合，边只连接不同集合中的顶点，这种约束使其连通性表现出独特规律。
3.3.1 连通二分图
若一个二分图在满足分组约束的同时仍能保证任意两点可达，则称为连通二分图。其连通性并不依赖于顶点是否属于同一集合，而取决于跨集合边是否形成整体路径网络。
3.3.2 相关判定特点
判断二分图是否连通，通常仍可借助遍历方法完成。同时还需检查顶点分组是否满足二分图的边连接规则。换言之，二分图的判定包含结构划分与连通性两个层面。
4 连通性的判定与算法
连通性的检测是图论中的常用任务，既可以用基础遍历实现，也可以配合专门的数据结构处理动态关系。
4.1 遍历算法
图遍历是判断连通性的最直接工具，其核心思想是从某个起点出发，尽可能访问所有可达顶点。
4.1.1 深度优先搜索
深度优先搜索会沿着一条路径尽可能深入，直到无法继续为止，再回溯到上一个分支继续探索。若从某个顶点出发，深搜能够访问到所有顶点，则图连通。该方法实现简单，适合用于连通分量的发现。
4.1.2 广度优先搜索
广度优先搜索按层次扩展访问范围，先处理距离起点较近的顶点，再逐步推进到更远位置。它同样可用于连通性检测，并且在最短路径相关任务中具有额外价值。
4.2 连通分量求解
当图非连通时，通常需要进一步找出各个连通分量，这在分析网络结构时十分常见。
4.2.1 图遍历标记法
图遍历标记法通过对访问过的顶点做标记，逐次从未访问顶点出发执行深搜或广搜，从而枚举所有连通分量。每完成一次遍历，就得到一个新的连通块。该方法直观且便于实现。
4.2.2 并查集方法
并查集适用于处理不断合并的集合关系。通过把边的两个端点所属集合进行合并，可以动态维护连通关系，并快速判断两个顶点是否属于同一连通分量。它在大量边操作场景中十分高效。
4.3 算法复杂度
连通性算法的效率通常以顶点数和边数为主要度量对象，复杂度分析是评估其适用性的关键。
4.3.1 时间复杂度分析
对于邻接表表示的图，深度优先搜索和广度优先搜索通常可在 O(V+E) 时间内完成，其中 V 为顶点数，E 为边数。并查集在配合路径压缩和按秩合并时，单次操作的均摊复杂度也非常低，适合大规模数据处理。
4.3.2 空间复杂度分析
遍历算法一般需要额外的访问标记数组，以及在递归或队列/栈中保存待处理顶点，因此空间开销与顶点数相关。并查集则主要消耗存储父节点与辅助秩信息的空间，整体较为紧凑。
5 进一步的连通性概念
在连通图的基础上，还可以进一步研究图在局部失效下的稳定性，这便引出了点连通度、边连通度等概念。
5.1 点连通度
点连通度关注的是删除顶点后图的连通状态，反映图对顶点失效的抵抗能力。
5.1.1 割点
割点是指删除该顶点及其关联边后，会使图的连通分量数增加的顶点。割点的存在意味着图在该位置具有结构上的薄弱环节，一旦移除，就可能造成分裂。
5.1.2 点连通图
点连通图通常指不存在割点，或者更一般地说，删除少量顶点后仍能保持连通的图。点连通度越高，图在顶点层面的稳定性通常越强。
5.2 边连通度
边连通度研究的是边被删除时图的连通性变化，体现图对连接关系破坏的耐受程度。
5.2.1 桥
桥是一条特殊的边，若删除它会使图的连通分量数增加，则称该边为桥。桥在图中往往承担关键连接作用，一旦失效，图可能被切成两个部分。
5.2.2 边连通图
边连通图是指删除少量边后仍能保持连通的图。边连通度刻画了图在边层面的冗余程度，常用于评估网络的可靠性。
5.3 相关定理
连通性研究中有若干经典定理，能够将路径、分离与结构稳定性联系起来。
5.3.1 Menger定理
Menger定理是图论中的重要结论之一，它建立了两点之间若干条内部点互不相交路径与最小点割之间的对应关系。该定理为点连通度与路径冗余之间的联系提供了理论基础。
5.3.2 连通性与分离条件
图是否连通，也可以从“能否通过删除少量顶点或边使其断开”这一角度理解。若存在较小的分离集，说明图结构较脆弱；若必须移除大量元素才能破坏连通，则图更为稳固。
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 交通与物流网络
交通路线和物流配送系统也常被抽象为图。连通性决定了站点之间能否形成完整运输链路，而桥、割点等概念则有助于识别关键枢纽与脆弱环节。