Breadth-First Graph Traversal

'''
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))