python - 如何使用递归获取节点邻居？

Question

我对递归函数很陌生，我尝试使用递归函数在图中获取节点邻居，图看起来像这样。

我想要获得此图中每个节点的邻居的序列。

首先，获取顶部第一个树节点的邻居。

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
            ]

而且我真的不知道如何使用递归函数完成剩下的工作。

Answer 1

此方法不使用递归，但我认为最好的办法是跟踪您知道的节点、您已经检查过的节点，并遍历您知道但未检查过的节点还没有。

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'}}