Getting neighbours in given distance BFS algorithm

Question

I have to write a function that will return a set that contains neighbours of a source vertex in given distance. For example for exemplary graph:

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

By passing this graph to a function + the source vertex which is 0 and passing distance = 2 the result should be: {1,2,3,4}.

How can I achieve that?

Answer 1

I am not well versed in graph theory, but the following seems to get correct results. It gets the following for a distance of 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()

Update: Wikipedia has a Python function here that implements a BFS algorithm.

Update: See also BFS algorithm in Python