如何在无向图中找出从任意节点可达的所有节点（连通分量识别）-Python教程-PHP中文网

如何在无向图中找出从任意节点可达的所有节点（连通分量识别）

本文介绍如何通过深度优先搜索（dfs）识别无向图中的所有连通分量，从而确定从任一节点出发可访问的全部节点集合；提供清晰的python实现、邻接矩阵适配方案及关键注意事项。

本文介绍如何通过深度优先搜索（dfs）识别无向图中的所有连通分量，从而确定从任一节点出发可访问的全部节点集合；提供清晰的python实现、邻接矩阵适配方案及关键注意事项。

在无向图中，“从某个节点能访问哪些节点”本质上是连通性分析问题——即判断图中节点间的可达关系。若两个节点之间存在路径，则它们属于同一连通分量（Connected Component）。整个图可被划分为若干互不连通的极大连通子图，每个子图内的任意两节点均可互相到达，而不同子图间则完全隔离。

以问题中给出的 5 节点图为例（节点标记为 A–E），其邻接矩阵表示如下：

    A B C D E
A [ 0 0 0 1 0 ]
B [ 0 0 1 0 0 ]
C [ 0 1 0 0 0 ]
D [ 1 0 0 0 1 ]
E [ 0 0 0 1 0 ]

直观可见：A–D–E 构成一个三角链式结构（A↔D↔E），B↔C 形成独立边。因此图包含两个连通分量：{A, D, E} 和 {B, C}。我们的目标就是自动识别并分组这些节点集合。

核心算法：基于 DFS 的连通分量标记

我们采用深度优先搜索遍历每个未访问节点，并递归标记其所有可达邻居，每完成一次完整遍历即发现一个新连通分量。为便于区分，我们为每个分量分配唯一整数编号（如 1, 2, 3…），最终返回每个节点对应的分量 ID。

以下是健壮、可读性强的 Python 实现（兼容邻接矩阵输入）：

def find_connected_components(adj_matrix):
    """
    输入：n x n 邻接矩阵（list of lists），值为 0/1
    输出：长度为 n 的列表，components[i] 表示节点 i 所属分量编号（从 1 开始）
    """
    n = len(adj_matrix)
    components = [0] * n  # 0 表示未访问
    current_component = 1

    def dfs(node):
        components[node] = current_component
        # 遍历所有可能邻居（按索引 0~n-1）
        for neighbor in range(n):
            if adj_matrix[node][neighbor] == 1 and components[neighbor] == 0:
                dfs(neighbor)

    # 对每个未访问节点启动 DFS
    for node in range(n):
        if components[node] == 0:
            dfs(node)
            current_component += 1

    return components

# 示例使用
adj = [
    [0, 0, 0, 1, 0],  # A
    [0, 0, 1, 0, 0],  # B
    [0, 1, 0, 0, 0],  # C
    [1, 0, 0, 0, 1],  # D
    [0, 0, 0, 1, 0],  # E
]

labels = ['A', 'B', 'C', 'D', 'E']
comp_ids = find_connected_components(adj)
result_map = dict(zip(labels, comp_ids))

print("分量编号:", comp_ids)           # [1, 2, 2, 1, 1]
print("节点映射:", result_map)        # {'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1}

# 进一步聚合为连通分量列表
from collections import defaultdict
groups = defaultdict(list)
for node, cid in enumerate(comp_ids):
    groups[cid].append(labels[node])
print("连通分量:", dict(groups))       # {1: ['A', 'D', 'E'], 2: ['B', 'C']}

关键说明与最佳实践

✅ 时间复杂度：O(V²)，其中 V 是节点数。邻接矩阵需检查每行所有列；若改用邻接表（推荐大规模图），可优化至 O(V + E)。
⚠️ 避免重复递归陷阱：务必用 components[neighbor] == 0 判断是否已访问，否则可能陷入死循环（尤其在含自环或多重边时需额外处理）。

? 起始节点无关性：该算法自动覆盖全图，无需指定“起点”——它会发现所有分量。若你仅需某一起点（如“A”）的可达节点，可简化为单次 DFS 并返回访问集合（见下方速查版）：

def reachable_from(adj_matrix, start_node):
    visited = set()
    stack = [start_node]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in range(len(adj_matrix)):
                if adj_matrix[node][neighbor] and neighbor not in visited:
                    stack.append(neighbor)
    return visited
print(reachable_from(adj, 0))  # 起点 A（索引0）→ {0, 3, 4} → {'A','D','E'}