rekursive Funktion zum Zurückgeben einer Liste aller verbundenen Knoten, gegeben einen bestimmten Knoten aus Netzwerkdiagramm mit Python

Question

Ich versuche, eine Funktion zu schreiben, die eine Liste aller verbundenen Knoten in einem Sub-Netzwerk zurückgibt, bei einem Start Knoten von Subgraphen:

zum Beispiel das zeigt dieses Diagramm zwei Teilnetze hat, eine rote und eine grüne, wie in der folgenden Abbildung dargestellt:

python-Paket namens NetworkX mit, ich habe hat den folgenden Code ausgeführt:

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) 

Die Funktion soll die Untergruppe -> [1,2,3,5] zurückgeben, wenn sie (1) als Startknoten angegeben wird, aber sie gibt [1,2,3,1,2,3] zurück

Irgendwelche Ideen, wie ich diese Aufgabe ausführen kann, indem Sie den Code optimieren oder vielleicht eine andere Methode verwenden?

Danke!

Answer 1

Falls Sie sich nicht daran interessiert, über die Reihenfolge der Knoten, die Sie gerade tun DFS besucht werden könnten und sammeln besuchten Knoten zu 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}