# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }


def bfs(graph, start, end):
    queue = [start]
    visited = []
    path = [None for num in range(15)]
    while not len(queue) == 0:
        node = queue.pop(0)
        visited.append(node)
        
        neighbors = graph.get(node,[])

        for neighbor in neighbors:
            if not neighbor in visited:
                queue.append(neighbor)
                path[int(neighbor)] = int(node)
                if neighbor == end:
                    return path

    
    return path

path = bfs(graph, '1', '11')

def doPath(path, end):
    # iterate backwards starting from the end
    current = path[int(end)]
    myPath = [int(end)]
    while not current == None:
        myPath.append(current)
        current = path[int(current)]

    myPath.reverse()
    print(myPath)
    return myPath

doPath(path, '11')




























# def bfs(graph, start, end):
#     # maintain a queue of paths
#     queue = []
#     # push the first path into the queue
#     queue.append([start])
#     while queue:
#         # get the first path from the queue
#         path = queue.pop(0)
#         # get the last node from the path
#         node = path[-1]
#         # path found
#         if node == end:
#             return path
#         # enumerate all adjacent nodes, construct a new path and push it into the queue
#         for adjacent in graph.get(node, []):
#             new_path = list(path)
#             new_path.append(adjacent)
#             queue.append(new_path)

# print(bfs(graph, '1', '11'))


