A generic breadth first traversal function

[Gribouillis]

The function breadth_first() defined below generates the nodes of a directed graph in breadth first order. Repeated nodes are ignored: only the first occurrence is generated.

from collections import deque
from itertools import chain
from more_itertools import unique_everseen

__version__ = '2019.07.07.1'

def consume(d, start, neighbors):
    yield (start,)
    while d:
        yield neighbors(d.popleft())


def breadth_first(start, neighbors):
    """Generates nodes of a directed graph in level order.
     
    Arguments:
        * start     : an arbitrary initial element (any hashable object)
        * neighbors : a function such that neighbors(item) is a sequence
                    of the item's neighbors in the graph.
                    
    Returns:
        A sequence of nodes in level order. Duplicate nodes are ignored:
        only the first occurrence is generated.
    """
    d = deque()
    for item in unique_everseen(
            chain.from_iterable(consume(d, start, neighbors))):
        yield item
        d.append(item)

if __name__ == '__main__':
    D = {
        1: [2, 3, 4],
        2: [5, 6],
        4: [7, 8],
        5: [9, 10, 4],
        7: [11, 12],
    }
    for x in breadth_first(1, lambda n: D.get(n, ())):
        print(x, end=' ')
    print()

Output:
1 2 3 4 5 6 7 8 9 10 11 12

Edit: A small improvement of version 2019.07.07 is to postpone the call to neighbors() as much as possible.

[perfringo]

Just for historical reference I add link to Guido van Rossum essay Python Patterns—Implementing Graphs

[rootVIII]

ah more_itertools is pretty neat