A concise implementation of breadth-first search (BFS) in Python.

bfs.py

"""
Assume we have a graph modeled as a dictionary like so:
graph = {
  'a': ['b', 'c'],
  'b': ['d'],
  'c': ['e'],
  'd': ['f'],
  'e': [],
  'f': []
}

bfs will traverse this graph using breadth-first search.
"""

from collections import deque

def bfs(graph, source):
    queue = deque([source])

    while len(queue) > 0:
        # Remove an element from the queue.
        current = queue.popleft()
        print(current)

        for neighbor in graph[current]:
            queue.append(neighbor)