Editor

Breadth-first search (BFS) in Python

Breadth-first search explores a graph level by level: the start node first, then every node one edge away, then two edges away. A queue keeps the nodes waiting in the order they were found.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. Start with start marked in visited and waiting in queue.
  2. Take the oldest node from the front of the queue with popleft() and add it to order.
  3. Every neighbour that is not in visited yet is marked and added to the back of the queue.
  4. Repeat until the queue is empty. Nodes come out level by level: A, then the nodes one edge away (B, C), then two edges away (D, E, F).

What to watch

  • Watch queue: new nodes join at the right end and leave from the left end, first in, first out.
  • Watch F: it is found from C first, so when E looks at it, it is already in visited and is not queued twice.
  • Watch the call stack stay flat: BFS is a loop, not recursion.

The code

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}

def bfs(graph, start):
    visited = {start}           # found already: never queue twice
    queue = deque([start])      # found, waiting to be explored
    order = []
    while queue:
        node = queue.popleft()  # the oldest node in the queue
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

print(bfs(graph, "A"))
Output
['A', 'B', 'C', 'D', 'E', 'F']

Open it in the editor · Python Program for Breadth-First Search on a Graph, explained