Necesitamos tu ayuda para difundir nuestros artículos acerca de las ciencias informáticas.
Solución:
Suponiendo que el gráfico no está dirigido, hay un comando networkx incorporado para esto:
node_connected_component(G, n)
La documentación está aquí. Devuelve todos los nodos en el componente conectado de G que contiene n.
No es recursivo, pero no creo que realmente necesites o incluso quieras eso.
comentarios sobre tu código: Tienes un error que a menudo resultará en una recursividad infinita. Si u y v son vecinos ambos con grado al menos 2, entonces comenzará con uponer v en la lista y al procesar v poner u en la lista y seguir repitiendo. Necesita cambiar para procesar solo a los vecinos que no están en neighbors_list. Es costoso verificar eso, así que en su lugar use un conjunto. También hay un pequeño problema si el nodo inicial tiene el grado 1. Su prueba para el grado 1 no hace lo que busca. Si el nodo inicial tiene el grado 1, pero su vecino tiene un grado mayor, no encontrará los vecinos del vecino.
Aquí hay una modificación de su código:
def fetch_connected_nodes(G, node, seen = None):
if seen == None:
seen = set([node])
for neighbor in G.neighbors(node):
print(neighbor)
if neighbor not in seen:
seen.add(neighbor)
fetch_connected_nodes(G, neighbor, seen)
return seen
Llamas a esto como fetch_connected_nodes(assembly, starting_node).
Simplemente puede usar una búsqueda en amplitud comenzando desde su nodo dado o cualquier nodo.
En Networkx puede tener el gráfico de árbol desde su nodo inicial usando la función:
bfs_tree(G, source, reverse=False)
Aquí hay un enlace al documento: Network bfs_tree.
Aquí hay un algoritmo recursivo para conectar todos los nodos a un nodo de entrada.
def create_subgraph(G,sub_G,start_node):
sub_G.add_node(start_node)
for n in G.neighbors_iter(start_node):
if n not in sub_G.neighbors(start_node):
sub_G.add_path([start_node,n])
create_subgraph(G,sub_G,n)
creo que el key La cosa aquí para evitar llamadas recursivas infinitas es la condición para verificar que el nodo que es vecino en el gráfico original no esté ya conectado en el sub_G que se está creando. De lo contrario, siempre estará yendo y viniendo y bordeando entre nodos que ya tienen bordes.
Lo probé de la siguiente manera:
G = nx.erdos_renyi_graph(20,0.08)
nx.draw(G,with_labels = True)
plt.show()
sub_G = nx.Graph()
create_subgraph(G,sub_G,17)
nx.draw(sub_G,with_labels = True)
plt.show()
Encontrará en la imagen adjunta, el gráfico completo y el sub_gráfico que contiene el nodo 17.
Recuerda que tienes concesión de agregar una reseña si encontraste tu cuestión .