import collections

from pygraph.graphdemo import Graph


def bfs(g: Graph, start: int) -> {int:int|None}:
    """

    :param g:
    :param start:
    :return:
    """
    tree = Graph()
    queue = collections.deque()
    VISITED = "visited"
    not_visited = {VISITED: False}
    visited = {VISITED: True}
    g.for_each_vertices(lambda v : g.merge_attribute(v, not_visited))
    queue.append(start)  # append() is the enqueue() operation of a Queue
    g.merge_attribute(start, visited)
    while queue:
        u = queue.popleft()  # popleft() is the dequeue() operation of a Queue
        for v in g.adjacent_of(u):
            if not g.get_attribute(v)[VISITED]:
                tree.add_edge(u, v)
                g.merge_attribute(v, visited)
                queue.append(v)
    return tree