BFS returning path

bfs.py

from collections import deque


def bfs(graph, start, goal):
    # initialize state
    queue = deque()
    explored_vertex_to_path = {}

    # utility functions
    def mark_as_explored(vertex, parent=None):
        if parent is None:
            explored_vertex_to_path[vertex] = [vertex]
        else:
            explored_vertex_to_path[vertex] = explored_vertex_to_path[parent] + [vertex]

    def was_explored(vertex):
        return vertex in explored_vertex_to_path

    def enqueue(vertex):
        queue.append(vertex)

    def dequeue():
        return queue.popleft()

    # algorithm implementation
    # (as close to pseudocode as possible https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode)
    mark_as_explored(start)
    enqueue(start)
    while queue:
        v = dequeue()

        if v == goal:
            return explored_vertex_to_path[v]

        neighbors = graph[v]
        for w in neighbors:
            if not was_explored(w):
                mark_as_explored(w, parent=v)
                enqueue(w)

    # error handling
    raise ValueError(f"No path from {start=} to {goal=}")


# CLI
# ----------------------------------------------------------------------

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


def main():
    graph = choose_graph()
    start = choose_int("start")
    goal = choose_int("goal")

    path = bfs(
        graph,
        start,
        goal
    )

    print(f"found path between {start=} and {goal=}: {path}")


def choose_graph():
    choices = '\n'.join(f"{key}: {graph}" for key, graph in GRAPHS.items())
    graph_num = int(input(f"Choose graph:\n{choices}\n"))

    return GRAPHS[graph_num]


def choose_int(name):
    return int(input(f"Choose {name}: "))


if __name__ == "__main__":
    main()