图中的孤立组

Question

我想写一段代码来检测图中的节点组。例如，请参见所附图片。我在那里绘制了一个包含 3 组节点的图表。算法的结果应该是 {0, 1, 2}, {3, 4 ,6 ,7}, {5, 8}.

我的直觉是运行为每个标记找到的节点（它可以到达的节点）的每个节点使用 DFS 算法，如果我对节点 0 执行此操作，它将标记节点 1 和 2。如果我运行它然后对于节点 1 它将找到 none 因为其组中的所有节点都已被标记。每个节点DFS发现的每组节点将是一组。最后我会保留非空组。

我的问题是：我可以使用某种聚类算法找到组吗？

测试图代码：

import networkx as nx
g = nx.Graph()

g.add_edge(0, 1)
g.add_edge(1, 2)

g.add_edge(6, 7)
g.add_edge(4, 7)
g.add_edge(3, 4)

g.add_edge(5, 8)


from matplotlib import pyplot as plt
nx.draw(g)

plt.show()

编辑

正如下面评论的那样，答案是：

from networkx import connected_components
connected_components(g)

Answer 1

networkx 的 connected_components 功能是您要找的吗？从图表中，它 returns 列表生成器，每个生成的项目都是连接节点的列表。

图中的孤立组

isolated groups in a graph

python

networkx