如何将一个不相连的networkx图分成多个相互不相交但相连的图？

Question

我有一个networkx.Graph表示一个图的对象，其节点表示英语单词，其两个 wnode 之间的边意味着这些节点表示的两个单词在其同义词集之间至少有一个共享的认知同义词（即非空交集）。我希望这对某人来说是有趣或有用的背景，但我的问题是一个与图、Python 相关的更广泛适用的问题。networkx

该图的许多诱导子图（边诱导或顶点诱导）都是边不相交和顶点不相交，我想将这些子图分成它们自己的networkx.Graph对象，以便它们连接且相互不相交。我可能只是在networkx文档中使用了错误的搜索词，但我没有看到任何与 "disjoint" 相关的有前途的内容。以下是来自图表一小部分的一些示例。

我查看了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图分成多个相互不相交的连接图？

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)]