如何使用递归获得节点邻居?

2024-03-28 12:02:07 发布

您现在位置:Python中文网/ 问答频道 /正文

我对递归函数很新,我试着用递归函数得到图中的节点邻居,图是这样的。你知道吗

我想要得到图中每个节点的邻居的序列。你知道吗

首先,获取顶部第一个树节点的邻居。你知道吗

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

这是我的问题

接下来,获取前一个邻居的邻居,获取节点邻居的顺序是首先使用all list的第一个索引(list in sub_node),然后再次使用all list的下一个索引,直到超出索引。 如果使用sub_node执行do,则会有如下输出。你知道吗

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
            ]

我真的不知道如何做过去的休息和使用递归函数。你知道吗


Tags: innodegetindex节点顺序neighbors序列
1条回答
网友
1楼 · 发布于 2024-03-28 12:02:07

这个方法不使用递归,但我认为最好的方法是跟踪您知道的节点,您已经检查过的节点,并遍历您知道但尚未检查过的节点。你知道吗

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

相关问题 更多 >