Как получить соседей узла с помощью рекурсии? - PullRequest
Новая
       11

Как получить соседей узла с помощью рекурсии?

4 голосов
/ 25 октября 2019

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

Последовательность, которую я хочуполучить соседей каждого узла в этом графе.

Сначала найдите соседей первого узла дерева сверху. 

sub_node = [
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors
            ]

Вот моя проблема

Далее получите соседей предыдущих соседей. и порядок получения соседей по узлам сначала выполняется с первым индексом всего списка (список в sub_node), затем снова со следующим индексом всего списка, пока не выйдет из индекса. если сделать с sub_node будет иметь такой вывод. 

sub_node = [ 
             #first
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors

             #second --> do with first index in tree list above
             [J, K],    #D neighbors
             [L],       #F neighbors
             [L],       #H neighbors

             # --> second index
             [K, L], #E neighbors
             [G],    #L neighbors
             [M],    #I neighbors

             # --> third index
             [L], #F neighbors
             [L], #H neighbors

            ]

Это мой код, и я использую библиотеки графов, это NetworkX. В моей функции и в первую очередь он идентифицирует узел initail. 

import networkx as nx

G = nx.Graph()

G.add_edges_from([('A', 'D'), ('A', 'E'), ('A', 'F'), 
                ('B', 'F'), ('B', 'G'), ('B', 'H'), 
                ('C', 'H'), ('C', 'I'), 
                ('D', 'J'), ('D', 'K'), 
                ('E', 'K'), ('E', 'L'), 
                ('F', 'L'), 
                ('G', 'L'), 
                ('H', 'L'), 
                ('I', 'M')
                ])


def get_neighbors(G, initial_node):
    sub_node = []
    for n in initial_node:
        sub_node.append(list(nx.neighbors(G, n)))


initial_node = ['A', 'B', 'C'] #identify initial node first.
get_neighbors(G, initial_node)

Теперь я могу выполнять только эту часть. 

sub_node = [
             [D, E, F], #A neighbors
             [F, G, H], #B neighbors
             [H, I],    #C neighbors
            ]

И я действительно не знаю, как сделать остальное в прошлом. и используя функцию рекурсии.

1 Ответ

0 голосов
/ 26 октября 2019

Этот метод не использует рекурсию, но я думаю, что вам лучше всего следить за узлами, о которых вы знаете, узлами, которые вы уже проверили, и перебирать узлы, о которых вы знаете, но не проверялипока. 

import networkx as nx

# initially setting up the graph
G = nx.Graph()
G.add_edges_from([('A', 'D'), ('A', 'E'), ('A', 'F'), 
                ('B', 'F'), ('B', 'G'), ('B', 'H'), 
                ('C', 'H'), ('C', 'I'), 
                ('D', 'J'), ('D', 'K'), 
                ('E', 'K'), ('E', 'L'), 
                ('F', 'L'), 
                ('G', 'L'), 
                ('H', 'L'), 
                ('I', 'M')
                ])

current_nodes = set(['A', 'B', 'C'])  # our list of known nodes
checked_nodes = set()  # our list of checked nodes

node_neighbors = {}
while len(current_nodes - checked_nodes) > 0:
    # first, randomly select a new node that we know about AND haven't already checked:
    current_node = (current_nodes - checked_nodes).pop()
    # get the neighbors of the node as unique elements:
    neighbors = set(nx.neighbors(G, current_node))

    # add any results we don't already know about to our list of known nodes:
    current_nodes |= neighbors  
    # save our results for this node:
    node_neighbors[current_node] = neighbors
    # finally, mark that we checked the node so we don't check it again:
    checked_nodes.add(current_node)

print(node_neighbors)
# {'C': {'H', 'I'}, 'H': {'C', 'B', 'L'}, 'B': {'G', 'F', 'H'}, 'L': {'G', 'F', 'E', 'H'}, 'A': {'F', 'E', 'D'}, 'D': {'A', 'K', 'J'}, 'J': {'D'}, 'K': {'E', 'D'}, 'G': {'B', 'L'}, 'F': {'B', 'A', 'L'}, 'E': {'A', 'K', 'L'}, 'I': {'M', 'C'}, 'M': {'I'}}
...