弱连通图是图论中用于刻画有向图连通程度的概念：把有向图每条边的方向去掉，所得的无向图称为底图（基图），若底图连通，则该有向图称为弱连通图。[1][2] 在有向图的三种连通性中，强连通与单向连通都蕴含弱连通，反之不成立。[1] 弱连通性只要求忽略方向后整体连成一片，常被用来了解一个网络的整体连通状况，也是计算弱连通分量的依据。[3]
定义
弱连通图是就有向图而言的。将一个有向图中每条弧的方向都去掉，得到的无向图称为该有向图的底图，也称基图或基础图；如果这个底图是连通的，原来的有向图就称为弱连通图。[1][2][4] 部分教材把这种情形下的有向图直接简称为连通图。[5]
也可以从顶点之间的路径来表述：如果对图中任意两个顶点，都能找到一条不要求处处顺着箭头方向走的路径把它们连起来，那么该有向图就是弱连通的。[6][7] 无向图一般只讨论连通与否，弱连通这一说法主要出现在有向图的情形中。[2]
弱连通的有向图未必是单向连通图或强连通图：凡强连通的图一定单向连通，凡单向连通的图一定弱连通，而这两个命题反过来都不成立。[1][5] 因此弱连通是有向图三种连通性中要求最低的一种。[1]
原理
判定一张有向图是否弱连通，最直接的做法是忽略方向，把每条弧视作无向边，再从任一顶点出发做一次广度优先搜索或深度优先搜索；如果能够访问到所有顶点，就说明该图弱连通。[8][4] 用符号表示，设有向图 $D=(V,E)$ 去掉弧的方向后得到的底图为 $G=(V,E')$，则 $D$ 弱连通当且仅当 $G$ 是连通的。[4]
下面这个 3 个顶点的有向图可以说明弱连通与强连通的差别：忽略方向后它是一条连通的链，所以是弱连通图；但顶点 1 与顶点 3 之间没有任何有向路径，因此它不强连通，也不单向连通。[1]
graph LR
A((1)) --> B((2))
C((3)) --> B
弱连通关系具有自反性、对称性和传递性，是一种等价关系，因此有向图的顶点集合可以被不重复地划分成若干个弱连通类。[9] 这些类对应的子图称为弱连通分量或弱分支，它们是极大的弱连通子图，也就是底图的连通分量，图中每个顶点恰好属于一个弱连通分量。[10][2]
发展历程
对图的研究可以追溯到 1736 年欧拉对哥尼斯堡七桥问题的解答，此后关于点与线连接关系的理论逐步发展成独立的数学分支。[11] 有向图的边带有方向，顶点之间的可达关系不再对称，连通性因此被分为强连通、单向连通和弱连通三个层次。[1]
求连通分量的算法很早就有了系统方法。1964 年，Bernard A. Galler 与 Michael J. Fischer 最早描述了并查集(union-find)这一数据结构，[8] 它与广度优先、深度优先遍历一起，成为计算弱连通分量的常用手段。[8]
当图的规模很大、顶点与边无法装入单机内存时，常规的深度优先搜索等方法难以直接使用。[12] 2010 年公开的一项专利申请提出在MapReduce框架下并行计算大规模图的弱连通分量：先由多个映射任务在各自收到的边集上求出子图的连通分量，再由归约任务合并，得到整个图的极大弱连通分量。[12] 近年图数据库与分析平台也把弱连通分量列为标准算法，例如 Amazon Neptune Analytics 的图算法库提供了 WCC 过程。[3]
应用
弱连通分量常常是图分析的预处理步骤：如果输入图本身不连通，算法可能只在其一部分上运行而给出难以察觉的错误结果，因此通常先做一次连通性检查。[8] 在有向图的欧拉回路判定中，弱连通性也是最基本的必要条件——图若不弱连通，就不可能存在经过每条边恰好一次的欧拉回路。[10]
在具体领域里，弱连通分量可以用来发现交通网络中没有与其他部分连成一片的区域，识别社交网络中互动范围有限的孤立用户群，以及在网页链接分析中定位可达性偏低的部分。[3] 数据库记录去重等主数据管理任务会用到并查集式的弱连通分量计算，引用网络分析中也有借助弱连通分量衡量网络连通程度的做法。[8]
在软件工程中，把函数调用、类与包的依赖关系建成有向网络之后，包依赖网络和类依赖网络中的最大弱连通子图可以用来表示面向对象软件系统的结构，弱连通图的连通强度与连通长度还被用于度量这种结构的质量。[13] 部分代码分析工具同样把弱连通分量列入结构分析算法，用来观察模块之间的整体关联情况。[14]
局限
弱连通是三种有向连通性中要求最低的一种，它只说明忽略方向后图连成一片，并不保证任意两个顶点之间存在有向路径。[1][6] 所以凡是关心传播方向、依赖方向或执行顺序的问题，仅凭弱连通性通常得不到结论，需要进一步要求单向连通或强连通。[1]
忽略方向也会丢失信息。每个强连通分量都完整地落在某一个弱连通分量之内，因此按弱连通分量划分得到的结果比按强连通分量划分更粗，无法用来说明两个顶点之间谁可以到达谁。[10][9]
计算大规模图的弱连通分量也有代价。当顶点与边的集合无法放入单机内存时，常用的深度优先搜索等方法不再适用，需要借助分布式或并行计算框架。[12] 以 Amazon Neptune Analytics 为例，其弱连通分量算法的时间复杂性为 $O(|E|\log D)$，其中 $|E|$ 为边数、$D$ 为图的直径，算法的运行需要处理图中的边。[3]
参见
参考资料
- [科普中国]-单向连通图 . kepuchina.cn [引用日期2026-09-29]
- 弱连通图 . baidu.com [引用日期2026-09-29]
- Weakly connected components algorithm . amazon.com [引用日期2026-09-29]
- 1 Digraphs . rpi.edu [引用日期2026-09-29]
- 对于任何图 \( G \)，皆有 \( k(G) \leq \lambda(G) \leq \delta(G) \) . tup.com.cn [引用日期2026-09-29]
- Connectivity (graph theory) . epfl.ch [引用日期2026-09-29]
- WeaklyConnectedGraphQ . wolframcloud.com [引用日期2026-09-29]
- Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook-EN-US(PDF) . neo4j.com [引用日期2026-09-29]
- content . ac.za [引用日期2026-09-29]
- video-3-1-verbose(PDF) . github.io [引用日期2026-09-29]
- 第二编 图论 . github.io [引用日期2026-09-29]
- US20100083194 . google.com [引用日期2026-09-29]
- 成果检索-武汉大学|机构知识库 - 基于软件网络的面向对象软件演化复杂性研究 . whu.edu.cn [引用日期2026-09-29]
- Graph Commands . github.io [引用日期2026-09-29]
浏览次数：1 次
阅读量：0 次 · 阅读完成量：0 次
最近更新：2026-09-29T11:12:48Z
完成率 = 阅读完成量 ÷ 阅读量，分母是阅读量不是浏览次数 —— 关了 JS 的、秒退的都在浏览次数里、不在阅读量里。 详细口径在后台的「数据统计」页。