本文介绍如何通过深度优先搜索算法，从任意起始节点出发，找出无向图中所有可达节点，并进一步识别整个图的连通分量——即彼此可达的节点集合。适用于邻接矩阵或邻接表表示的图，附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 实现（适配邻接矩阵输入）：
def find_connected_components(adj_matrix):
"""
返回每个节点所属的连通分量编号（从1开始）
输入：adj_matrix —— n×n 邻接矩阵，元素为0/1
输出：长度为n的列表，components[i] 表示节点i的分量ID
"""
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 v in range(n):
if components[v] == 0:
dfs(v)
comp_id += 1
return components
# 示例调用
adj = [
[0, 0, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 1, 0]
]
result = find_connected_components(adj)
print("组件编号（索引顺序）:", result) # [1, 2, 2, 1, 1]
vertices = list("ABCDE")
mapping = dict(zip(vertices, result))
print("节点→组件映射:", mapping) # {'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1}
运行结果清晰表明：
- 分量 1：{'A', 'D', 'E'}
- 分量 2：{'B', 'C'}
✅ 关键注意事项：
- 本实现基于邻接矩阵，适合小规模稠密图；若图规模大或稀疏，建议改用邻接表（如 graph = {v: [u1, u2, ...]}），可显著提升遍历效率；
- DFS 使用递归，极端深图可能导致栈溢出；生产环境推荐改用显式栈的迭代 DFS 或切换为 BFS；
- 若仅需判断“从某节点 s 是否可达 t”，无需计算全部分量，可直接对 s 启动单次 DFS/BFS 并检查 t 是否在访问集合中；
- 对于有向图，此方法不适用——需使用 Kosaraju 或 Tarjan 算法求强连通分量（SCC）。
总结而言，连通分量分析是理解图结构的基石。掌握 DFS 的组件标记模式，不仅能解决“从某点出发能到哪”，更能系统揭示图的拓扑骨架。建议初学者先手动画出小图执行过程，再对照代码理解递归回溯与状态传播机制，逐步建立图算法直觉。
