Breadth-First Search (BFS)

Explore in rings

Breadth-first search starts at one vertex, visits all its neighbours, then all their neighbours, and so on – in rings that grow outward. It uses a queue.

Think of it like this: Dropping a stone in a pond: the ripples reach close points first, then points further away.

from collections import deque

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

def bfs(start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:            # not visited yet
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

print(bfs("A"))

Output

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

Because BFS visits vertices in order of distance, the first time it reaches a vertex is along a shortest path (fewest edges).

Remembering the path

from collections import deque

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

def shortest_path(start, goal):
    came_from = {start: None}
    q = deque([start])
    while q:
        node = q.popleft()
        if node == goal:
            break
        for nxt in graph[node]:
            if nxt not in came_from:
                came_from[nxt] = node
                q.append(nxt)
    path = []
    node = goal
    while node is not None:               # walk back from the goal
        path.append(node)
        node = came_from[node]
    return path[::-1]

print(shortest_path("D", "F"))

Output

['D', 'B', 'E', 'F']

Every vertex and edge is handled once: O(V + E), where V is the number of vertices and E the number of edges.

Common mistake: Forgetting to mark vertices as visited makes BFS go round in circles forever on a graph with a loop.