寻找节点的n阶邻居

Question

我是networkx的新手，实际上对如何有效地找到节点的n次邻域有点困惑。节点vui的n次邻域是距离vui正好n个跳的节点集，给定一个指定的n，我需要找到图/网络中每个节点的n次邻域。在

假设我有下面的图，我想找到节点v1的n=1邻域。那就是v2和v3。接下来假设我想找到节点v1的n=2邻域，那么它就是v4。在

Answer 1

查找给定节点的n个邻居的最有效方法是使用深度优先搜索： http://en.wikipedia.org/wiki/Depth-first_search。下面的函数返回所有距离的start的邻域。但是，如果需要为所有节点查找n个邻居，那么对所有节点使用此函数并不是最有效的解决方案。相反，我们可以只对每个连接的组件中的一个开始节点使用这个函数，并计算其他节点相对于起始节点的n个邻居，但这将相当复杂。在

import networkx as nx

def n_neighbor(G, start):

    #  {distance : [list of nodes at that distance]}
    distance_nodes = {}

    # nodes at distance 1 from the currently visited ones
    next_shell = G.neighbors(start)

    # set of all visited nodes
    visited=set()
    visited.add(start)

    # how fare we are from start
    distance = 0

    # until we run out of nodes
    while len(next_shell) > 0:

        # this will be the next shell
        shell_after_this = []

        # update distance
        distance += 1
        distance_nodes[distance] = []

        # update visited and distance_nodes
        for node in next_shell:
            visited.add(node)
            distance_nodes[distance].append(node)


        # compute shell_after_this
        for node in next_shell:
            # add neighbors to shell_after_this
            # if they have not been visited already
            for neighbor in G.neighbors(node):
                if neighbor not in visited:
                    shell_after_this.append(neighbor)

        # we repeat with the new_shell
        next_shell = set(shell_after_this)

    return distance_nodes


# example 
G=nx.Graph()

G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)
G.add_edge(2,4)
G.add_edge(3,5)
G.add_edge(5,17)
G.add_edge(2,6)

print n_neighbor(G, 1)    

Answer 2

import networkx as nx
G = nx.Graph()
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')])

def neighborhood(G, node, n):
    path_lengths = nx.single_source_dijkstra_path_length(G, node)
    return [node for node, length in path_lengths.iteritems()
                    if length == n]

print(neighborhood(G, 'v1', 1))
# ['v2', 'v3']
print(neighborhood(G, 'v1', 2))
# ['v4']

Answer 3

当您在图上执行宽度优先搜索时，从根节点r开始-节点被认为与r的距离在增加

因此，您只需要在执行BFS时跟踪节点的级别，请参见http://en.wikipedia.org/wiki/Level_structure以获得更深入的讨论。在