如何将一个未连接的NetworkX图分成多个互相不相交但是连通的子图？

Question

我有一个 networkx.Graph 对象，表示一个图形，其节点代表英语单词，两个节点之间的边缘意味着这两个节点所代表的单词之间至少有一个共享的认知同义词在它们的synsets（即非空交集）中。我希望这对某些人来说是有趣或有用的背景信息，但我的问题更普遍，涉及到图形、networkx 和 Python。

这个图的许多诱导子图（边诱导或点诱导）既是边不相交且点不相交的，我想将这些子图分离成它们自己的networkx.Graph对象，以便它们互相连接且互不相交。可能是因为我在networkx文档中使用了错误的搜索术语，但是我没有看到任何与“不相交”相关的有希望的内容。以下是该图的一小部分的一些示例。

我在Stack Overflow上查看了关于[networkx] disjoint的搜索结果，但没有找到我要找的内容。例如，一个结果讨论了当已经有一个边集可以诱导出时如何获得诱导子图。或者另一篇帖子讨论了尝试绘制两个不相交的图形, 但这是假设你已经有它们了。与我的问题相关的图论方面，但不是networkx方面，是显然有洪水填充算法可能解决我的问题的部分。

现在，为了创建一个最小化工作示例，让我们创建一个小的随机图，但确保它是不连通的。

import networkx as nx

g = nx.fast_gnp_random_graph(10, 0.3)

while nx.is_connected(g):
    g = nx.fast_gnp_random_graph(10, 0.3)

此时我们有一个名为g的图。我想要的是以下内容，其中我占据了一组彼此互不相交的图。我不仅需要在循环节点时添加更多图形，还需要随着进程更新这些图形。我认为诱导图的联合可能有效，但nx.disjoint_union_all和nx.union会强制通过重新标记使图形不相交（我不希望这样），或者期望图形已经不相交。

graphs = []

for node in g.nodes(): # same 'g' we made above
    if graphs:
        pass
    else:
        graphs.append(g.subgraph([i for i in g.neighbors(node)] +\
                                 [node]).copy())

如何将一个未连接的networkx图分成多个互不相交但仍然连接的子图？

- Galen

---

你的图是有向的吗？你在示例中展示的图是无向的，但你也使用了“弱连通”的术语，这意味着它是有向的。如果是无向的，请使用nx.connected_components。如果是有向的，请使用nx.connected_components(nx.Graph(G))（首先将其转换为无向）。 - Joel

哎呀，那是我的语言错误。我正在处理无向图。我会修正措辞。感谢反馈。看起来你有一个潜在的答案，请把它发布出来，这样如果有效的话我就可以接受它了！ :P - Galen

我现在很忙，所以非常乐意让其他人填写细节。我可能要几天才能回复。 - Joel

Answer 1

看起来你正在寻找连通分量。
考虑以下图形：

components = [g.subgraph(c).copy() for c in nx.connected_components(g)]
for idx,g in enumerate(components,start=1):
    print(f"Component {idx}: Nodes: {g.nodes()} Edges: {g.edges()}")

输出：

Component 1: Nodes: [0, 1, 2, 5, 6, 7, 8, 9] Edges: [(0, 2), (0, 6), (1, 2), (1, 5), (1, 7), (1, 8), (2, 5), (5, 7), (6, 8), (7, 9), (8, 9)]
Component 2: Nodes: [3, 4] Edges: [(3, 4)]

- abc