本文介绍如何通过深度优先搜索算法，从任意起始节点出发，找出无向图中所有可达节点，并进一步识别整个图的连通分量——即彼此可达的节点集合，适用于邻接矩阵或邻接表表示的图结构。
本文介绍如何通过深度优先搜索算法，从任意起始节点出发，找出无向图中所有可达节点，并进一步识别整个图的连通分量——即彼此可达的节点集合，适用于邻接矩阵或邻接表表示的图结构。
在无向图中，“从某节点出发能访问到哪些节点”本质上是连通性判定问题；而将全图划分为若干极大连通子图，则称为连通分量（Connected Components）识别。每个连通分量内的任意两个节点均存在路径相连，不同分量之间则完全不连通——这正是你示例中 {A, D, E} 与 {B, C} 的本质关系。
解决该问题的核心思路是：对每个未访问节点启动一次 DFS（或 BFS），遍历其可达的所有节点，并统一标记为同一分量编号。以下为基于邻接矩阵实现的 Python 示例（兼容初学者理解，无需额外依赖）：
def find_connected_components(adj_matrix):
"""
输入：n×n 邻接矩阵（元素为0/1，表示无边/有边）
输出：长度为n的列表，components[i] 表示节点i所属的连通分量编号（从1开始）
"""
n = len(adj_matrix)
components = [0] * n # 0 表示未访问
comp_id = 1
def dfs(v):
components[v] = comp_id
for u in range(n):
if adj_matrix[v][u] == 1 and components[u] == 0:
dfs(u)
for i in range(n):
if components[i] == 0:
dfs(i)
comp_id += 1
return components
# 示例图：节点索引 0→A, 1→B, 2→C, 3→D, 4→E
adj = [
[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
]
result = find_connected_components(adj)
node_names = ['A', 'B', 'C', 'D', 'E']
mapping = dict(zip(node_names, result))
print("分量编号:", result) # [1, 2, 2, 1, 1]
print("节点映射:", mapping) # {'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1}
✅ 关键说明与注意事项：
- 时间复杂度：O(V²)，适用于邻接矩阵；若改用邻接表（如 graph = {A: [D], B: [C], ...}），可优化至 O(V + E)；
- 空间优化建议：实际项目中推荐使用邻接表 + set 或布尔数组记录访问状态，避免递归过深（大型图可改用栈模拟 DFS 或切换为 BFS）；
- 命名映射：代码中通过 zip(node_names, result) 将数字结果映射为可读标签，便于调试与业务集成；
- 单点可达性查询：若仅需判断“从节点 X 能否到达 Y”，可对 X 启动一次 DFS/BFS 并检查 Y 是否被访问，无需计算全部分量。
总结而言，连通分量识别是图论的基础能力，DFS 是其实现最直观、教学友好的方案。掌握此方法后，你不仅能解析给定图的拓扑结构，还可延伸应用于社交网络圈子发现、图像连通区域分析、编译器变量依赖检测等真实场景。
