Как найти весь связанный подграф графа в сети x?

Question

Я занимаюсь разработкой приложения на Python и хочу перечислить все возможные подключенные подграфы любого размера, начиная с каждого узла, используя NetworkX.

Я просто попытался использовать комбинации () из библиотеки itertools, чтобы найти всевозможна комбинация узлов, но она слишком медленная, потому что она ищет также не подключенные узлы:

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 как LenghtTupleToFind составляют до 1 миллиарда (n! / R! / (Nr)!), Но только минимальная их частьподключенный подграф, так что это то, что меня интересует. Итак, есть возможность иметь функцию для этого?

Извините за мой английский, заранее спасибо

РЕДАКТИРОВАТЬ :

Это пример:

пример начального графика

Итак, результаты, которые я хотел бы получить:

[0]
[0,1]
[0,2]
[0,3]
[0,1,4]
[0,2,5]
[0,2,5,4]
[0,1,4,5]
[0,1,2,4,5]
[0,1,2,3]
[0,1,2,3,5]
[0,1,2,3,4]
[0,1,2,3,4,5]
[0,3,2]
[0,3,1]
[0,3,2]
[0,1,4,2]

и все комбинации, которые генерируют связный граф

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)