Function breadth_first_search

pattern/graph/__init__.py:708–720

Visits all the nodes connected to the given root node, breadth-first.

(node, visit=lambda node: False, traversable=lambda node, edge: True)

dfs = depth_first_search;

def breadth_first_search(node, visit=lambda node: False, traversable=lambda node, edge: True):
    """ Visits all the nodes connected to the given root node, breadth-first.
    """
    q = [node]
    _visited = {}
    while q:
        node = q.pop(0)
        if not node.id in _visited:
            if visit(node):
                return True
            q.extend((n for n in node.links if traversable(node, node.links.edge(n)) is not False))
            _visited[node.id] = True
    return False
        
bfs = breadth_first_search;