不使用nx.connected_components()查找NetworkX图连通分量的代码问题排查

问题描述 #

已使用NetworkX创建了一个无向图，需要获取所有连通分量的列表。尝试运行以下代码后，发现结果与nx.connected_components()命令的输出不一致，请问代码存在什么问题？

connected_components = {}
def dfs(node):
    global connected_components, G  
    if node not in connected_components:
        connected_components[node] = set()
        for next in G.adj[node]:
            dfs(next)
            connected_components[node] = connected_components[next]
        connected_components[node].add(node)

for node_ in G:
    dfs(node_)

connected_comp_as_tuples = map(tuple, connected_components.values())
unique_components = set(connected_comp_as_tuples)
CC=list(unique_components)

代码中的问题 #

• 邻接节点集合赋值逻辑错误：在遍历当前节点的邻接节点时，每次递归返回后都执行connected_components[node] = connected_components[next]，这会覆盖当前节点之前的集合引用。例如，若节点A有两个邻接节点B和C，处理完B后A的集合指向B的集合，处理C时又将A的集合替换为C的集合，最终A的集合只包含C的集合元素加上A本身，完全丢失了B所在的连通部分。
• 集合引用管理混乱：每个节点的集合没有共享同一连通分量的引用，而是被反复覆盖，导致同一个连通分量内的节点最终对应的集合不一致，后续通过去重得到的结果自然错误。
• 冗余的节点处理：循环遍历所有节点并调用dfs，虽然已处理的节点会跳过，但这种方式效率低下，且不是导致结果错误的核心原因。

修正后的代码 #

方式一：使用全局变量管理当前连通分量 #

connected_components = {}
current_component = None

def dfs(node):
    global connected_components, G, current_component
    if node not in connected_components:
        # 将当前节点关联到当前连通分量集合
        connected_components[node] = current_component
        current_component.add(node)
        for neighbor in G.adj[node]:
            dfs(neighbor)

for node in G:
    if node not in connected_components:
        # 遇到未访问节点，创建新的连通分量集合
        current_component = set()
        dfs(node)

# 提取唯一的连通分量集合
unique_components = list(set(connected_components.values()))

方式二：使用闭包避免全局变量（更推荐） #

def get_connected_components(G):
    visited = set()
    components = []
    
    def dfs(node, component):
        if node not in visited:
            visited.add(node)
            component.add(node)
            for neighbor in G.adj[node]:
                dfs(neighbor, component)
    
    for node in G:
        if node not in visited:
            comp = set()
            dfs(node, comp)
            components.append(comp)
    return components

# 调用函数获取连通分量
CC = get_connected_components(G)

修正逻辑说明 #

• 每次发现未访问的节点时，创建一个新的空集合用于存储该连通分量的所有节点。
• DFS遍历过程中，将所有可达节点加入同一个集合，并标记为已访问，确保同一连通分量的所有节点共享同一集合引用。
• 最终收集所有创建的集合，就是正确的连通分量列表，与nx.connected_components()的输出一致。

内容的提问来源于stack exchange，提问作者luisa