图论入门：使用深度优先搜索（DFS）识别无向图中的连通分量

本文介绍如何通过深度优先搜索算法从任意起始节点出发找出无向图中所有可达节点并进一步识别整个图的连通分量——即彼此可达的节点集合。适用于邻接矩阵或邻接表表示的图附python实现与详细解析。 本文介绍如何通过深度优先搜索算法从任意起始节点出发找出无向图中所有可达节点并进一步识别整个图的连通分量——即彼此可达的节点集合。适用于邻接矩阵或邻接表表示的图附python实现与详细解析。在无向图中“从某节点出发能访问哪些节点”本质上是连通性判定问题而将全图划分为若干互不连通的最大子集则称为连通分量Connected Components分解。这是图论中最基础且实用的操作之一广泛应用于社交网络分析、电路连通检测、图像分割及依赖关系建模等场景。给定一个无向图如题中 5 节点示例其邻接矩阵如下adjacency [ [0, 0, 0, 1, 0], # A: connected to D [0, 0, 1, 0, 0], # B: connected to C [0, 1, 0, 0, 0], # C: connected to B [1, 0, 0, 0, 1], # D: connected to A, E [0, 0, 0, 1, 0] # E: connected to D]观察可知A–D–E 构成一个连通子图B–C 构成另一个二者间无边连接。因此该图包含 2 个连通分量。我们采用深度优先搜索DFS 实现连通分量标记对每个未访问节点启动一次 DFS递归遍历其所有可达邻居并统一赋予相同组件编号。算法时间复杂度为 $O(V E)$邻接表或 $O(V^2)$邻接矩阵空间复杂度为 $O(V)$递归栈 标记数组。以下是完整、健壮的 Python 实现适配邻接矩阵输入 arXiv Xplorer ArXiv 语义搜索引擎帮您快速轻松的查找保存和下载arXiv文章。