获取给定距离的邻居 BFS 算法

Question

我必须编写一个函数，它将 return 一个 set 包含给定距离内源顶点的邻居。例如，对于示例图：

        {0: [1, 3],
         1: [2],
         2: [],
         3: [4],
         4: [1, 5],
         5: [],
         6: [1]}

通过将此图传递给函数 + 为 0 的源顶点并传递距离 = 2，结果应为：{1,2,3,4}.

我怎样才能做到这一点？

Answer 1

我对图论不是很精通，但下面的似乎得到了正确的结果。对于 2 的距离，它得到以下结果：

{1, 2, 3, 4}

import networkx as nx

def main():
    distance = 2
    source_node = 0

    dict1 = {0: [1, 3],
             1: [2],
             2: [],
             3: [4],
             4: [1, 5],
             5: [],
             6: [1]}

    g = nx.DiGraph()

    # fill graph
    for node, list1 in dict1.items():
        for n in list1:
            g.add_edge(node, n)

    neighbors = []
    M = [source_node]

    for _ in range(distance):
        M = find_neigbors(g,M)
        neighbors.extend(M)

    print(neighbors)

def find_neigbors(g, vertices):
    p = []
    for node in vertices:
        p.extend(g.adj[node])
    return p

main()

更新：维基百科有一个 Python 函数 here 实现了 BFS 算法。

更新：另见 BFS algorithm in Python

获取给定距离的邻居 BFS 算法

Getting neighbours in given distance BFS algorithm

python

breadth-first-search

graph-traversal