时间戳

首页 > 解决方案 > 在给定距离内获取邻居 BFS 算法

python - 在给定距离内获取邻居 BFS 算法

问题描述

我必须编写一个函数，该函数将返回一个set包含给定距离内源顶点的邻居的 a 。例如示例图：

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

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

我怎样才能做到这一点？

标签： pythonbreadth-first-searchgraph-traversal

解决方案

我不太精通图论，但以下似乎得到了正确的结果。它在距离为 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()

更新：维基百科在这里有一个实现 BFS 算法的 Python 函数。

更新：另见Python 中的 BFS 算法

推荐阅读