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

本文介绍如何通过深度优先搜索算法，从任意起始节点出发，找出无向图中所有可达节点，并进一步识别整个图的连通分量——即彼此可达的节点集合，适用于邻接矩阵或邻接表表示的图结构。 本文介绍如何通过深度优先搜索算法，从任意起始节点出发，找出无向图中所有可达节点，并进一步识别整个图的连通分量——即彼此可达的节点集合，适用于邻接矩阵或邻接表表示的图结构。在无向图中，“从某节点出发能访问到哪些节点”本质上是连通性判定问题；而将全图划分为若干极大连通子图，则称为连通分量（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→Eadj = [ [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}? 关键说明与注意事项： RedClaw 百度推出的手机端万能AI Agent助手