Breadth-First Graph Traversal
123456789101112131415161718192021222324252627282930
'''
returns the shortest path from a root node to a target node.
'''
graph = {
0: [1, 2, 3],
1: [4, 5],
2: [6, 7]
}
def bfs(g, root, target):
q = [[root]]
visited = set()
while q:
path = q.pop(0)
vertex = path[-1]
if vertex == target:
return path
elif vertex not in visited:
for node in g.get(vertex, []):
adj_path = list(path)
adj_path.append(node)
q.append(adj_path)
visited.add(vertex)
print(bfs(graph, 0, 6))
Python
INFO