BFS

bfs.py

# Ref. http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/


def bfs(graph, queue, visited=None):
    if visited is None:
        visited = set()
    if not queue:
        return
    start = queue.pop(0)
    yield start
    visited.add(start)
    queue += [vertex for vertex in graph[start] - set(queue) - visited]
    yield from bfs(graph, queue, visited=visited)


def bfs_paths(graph, queue, goal):
    if not queue:
        return
    (start, path) = queue.pop(0)
    if start == goal:
        yield path
    queue += [(vertex, path + [vertex]) for vertex in graph[start] - set(path)]
    yield from bfs_paths(graph, queue, goal)


graph = {
    'A': set(['B', 'C']),
    'B': set(['A', 'D', 'E']),
    'C': set(['A', 'F']),
    'D': set(['B']),
    'E': set(['B', 'F']),
    'F': set(['C', 'E']),
}

print(repr([vertex for vertex in bfs(graph, ['A'])]))
print(repr([path for path in bfs_paths(graph, [('A', ['A'])], 'F')]))