https:en.wikipedia.orgwikiBreadthfirstsearch pseudocode: breadthfirstsearchgraph G, start vertex s:  all nodes initially unexplored mark s as explored let Q  queue data structure, initialized with s while Q is nonempty: remove the first node of Q, call it v for each edgev, w:   for w in graphv if w unexplored: mark w as explored add w to Q at the end Implementation of breadth first search using queue.Queue.  ''.joinbreadthfirstsearchG, 'A' 'ABCDEF' Implementation of breadth first search using collection.queue.  ''.joinbreadthfirstsearchwithdequeG, 'A' 'ABCDEF' breadthfirstsearch                finished 10000 runs in 0.20999 seconds breadthfirstsearchwithdeque     finished 10000 runs in 0.01421 seconds
from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

G = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}


def breadth_first_search(graph: dict, start: str) -> list[str]:
    """
    Implementation of breadth first search using queue.Queue.

    >>> ''.join(breadth_first_search(G, 'A'))
    'ABCDEF'
    """
    explored = {start}
    result = [start]
    queue: Queue = Queue()
    queue.put(start)
    while not queue.empty():
        v = queue.get()
        for w in graph[v]:
            if w not in explored:
                explored.add(w)
                result.append(w)
                queue.put(w)
    return result


def breadth_first_search_with_deque(graph: dict, start: str) -> list[str]:
    """
    Implementation of breadth first search using collection.queue.

    >>> ''.join(breadth_first_search_with_deque(G, 'A'))
    'ABCDEF'
    """
    visited = {start}
    result = [start]
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for child in graph[v]:
            if child not in visited:
                visited.add(child)
                result.append(child)
                queue.append(child)
    return result


def benchmark_function(name: str) -> None:
    setup = f"from __main__ import G, {name}"
    number = 10000
    res = timeit(f"{name}(G, 'A')", setup=setup, number=number)
    print(f"{name:<35} finished {number} runs in {res:.5f} seconds")


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    benchmark_function("breadth_first_search")
    benchmark_function("breadth_first_search_with_deque")
    # breadth_first_search                finished 10000 runs in 0.20999 seconds
    # breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds
