如何在networkx中找到图的所有连通子图？

Question

我正在开发一个python应用程序，我想用NetworkX从每个节点开始列出所有可能的连接子图。在

我刚刚尝试使用itertools库中的combinations（）来查找所有可能的节点组合，但速度太慢，因为它还搜索未连接的节点：

for r in range(0,NumberOfNodes)
for SG in (G.subgraph(s) for s in combinations(G,r):
    if (nx.is_connected(SG)):
        nx.draw(SG,with_labels=True)
        plt.show()

实际输出正确。但我需要另一种更快的方法来实现这一点，因为图中包含50个节点和8个lenghtupletofId的节点的所有组合都高达10亿（n！/r！/（n-r）！）但其中只有一小部分是连通子图，所以我感兴趣的是。所以，有可能有一个函数来做这个？在

对不起我的英语，先谢谢你

编辑：

这是一个例子：

example of starting graph

所以，我想得到的结果是：

^{pr2}$

以及所有生成连通图的组合

Answer 1

我也有同样的要求，最后使用了这段代码，非常接近您所做的。这段代码生成的正是您所要求的输入。在

import networkx as nx
import itertools

G = you_graph
all_connected_subgraphs = []

# here we ask for all connected subgraphs that have at least 2 nodes AND have less nodes than the input graph
for nb_nodes in range(2, G.number_of_nodes()):
    for SG in (G.subgraph(selected_nodes) for selected_nodes in itertools.combinations(G, nb_nodes)):
        if nx.is_connected(SG):
            print(SG.nodes)
            all_connected_subgraphs.append(SG)

Answer 2

你可以在O（n）时间和内存复杂度中找到所有连接的组件。保留一个可见的布尔数组，并运行深度优先搜索（DFS）或面包优先搜索（BFS），以查找连接的组件。
在我的代码中，我使用DFS来查找连接的组件。在

seen = [False] * num_nodes
def search(node):
    component.append(node)
    seen[node] = True
    for neigh in G.neighbors(node):
        if not seen[neigh]:
            dfs(neigh)

all_subgraphs = []    

# Assuming nodes are numbered 0, 1, ..., num_nodes - 1
for node in range(num_nodes):
    component = []
    dfs(node)
    # Here `component` contains nodes in a connected component of G
    plot_graph(component)  # or do anything
    all_subgraphs.append(component)