BFS

BFS.py

"""BFS.py

Breadth First Search. See also LexBFS.py.

D. Eppstein, May 2007.
"""

try:
    set
except NameError:
    from sets import Set as set

def BreadthFirstLevels(G,root):
    """
    Generate a sequence of bipartite directed graphs, each consisting
    of the edges from level i to level i+1 of G. Edges that connect
    vertices within the same level are not included in the output.
    The vertices in each level can be listed by iterating over each
    output graph.
    """
    visited = set()
    currentLevel = [root]
    while currentLevel:
        for v in currentLevel:
            visited.add(v)
        nextLevel = set()
        levelGraph = dict([(v,set()) for v in currentLevel])
        for v in currentLevel:
            for w in G[v]:
                if w not in visited:
                    levelGraph[v].add(w)
                    nextLevel.add(w)
        yield levelGraph
        currentLevel = nextLevel