Рекурсивная функция для возврата списка всех подключенных узлов, заданных определенным узлом из сетевого графа с использованием python

Question

Я пытаюсь написать функцию, которая будет возвращать список всех подключенных узлов в подсети, учитывая начальный узел из подграфа:

например, следующий график имеет две подсети, одну красную и одну зеленую, как показано на следующем рисунке:

используя пакет python под названием networkx, я запустил следующий код:

import networkx as nx
import pandas as pd
import numpy as np

G=nx.Graph()

G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_node(6)

G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(1,5)
G.add_edge(4,6)

def recurse(G, z , node):
    z.append(node)
    n = list(set(G.neighbors(node)) - set(z)) 
    if len(n) == 0:
        return []
    else:
        for i in n:
            if i not in z:
                z.extend(recurse(G, z, i))
                return z

z = []
f = recurse(G,z,1)
print(f)

Функция должна возвращать подгруппу -> [1,2,3,5], когда задано (1) в качестве начального узла, но она возвращает [1,2,3,1,2,3]

Любые идеи, как я могу выполнить эту задачу путем настройки кода или, возможно, с помощью другого метода?

Спасибо!

Answer 1

Если вас не интересует порядок посещения узлов, вы можете просто сделать DFS и собрать посещенные узлы для set:

def recurse(G, z, node):
    z.add(node)
    for i in G.neighbors(node):
        if i not in z:
            recurse(G, z, i)

z = set()
recurse(G,z,1)
print(z) # {1, 2, 3, 5}