如何找到networkx图的连通分量？ （不使用 nx.connected_components() 命令）

Question

我使用networkx创建了一个无向图，我需要找到所有连接组件的列表。

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)

我尝试使用此代码，但结果与使用 nx.connected_components() 命令给出的结果不同。 我做错了什么？

Answer 1

每次运行循环时都会重置

connected_components[node]

设置。而不是

connected_components[node] = connected_components[next]

，它应该是类似于

connected_components[node] = connected_components[node].union(connected_components[next])

的东西。顺便说一句，目前还不清楚为什么你要自己写这个，但为了将来的参考，维基百科上有很好的 DFS 伪代码https://en.wikipedia.org/wiki/Depth-first_search.