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?
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
