🎓 A1Learner
🔍

DSA Breadth-First Search on Graphs

Breadth-first search is a graph walk that explores level by level from a start vertex. A queue holds the vertices waiting to be explored, in the order they were found.

BFS order

The queue serves vertices in the order they were found. Every neighbour of A is visited before any vertex two steps away.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F")]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])
from collections import deque
visited = {"A"}
order = []
queue = deque(["A"])
while queue:
    v = queue.popleft()
    order.append(v)
    for nxt in graph[v]:
        if nxt not in visited:
            visited.add(nxt)
            queue.append(nxt)
print(order)

BFS distances

Each vertex records the distance of the vertex that found it, plus one. The table below grows level by level.

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F")]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])
from collections import deque
dist = {"A": 0}
queue = deque(["A"])
while queue:
    v = queue.popleft()
    for nxt in graph[v]:
        if nxt not in dist:
            dist[nxt] = dist[v] + 1
            queue.append(nxt)
for name in sorted(dist):
    print(name, dist[name])

Example

from collections import deque

edges = [
    ("A", "B"), ("A", "C"), ("B", "D"),
    ("B", "E"), ("C", "F"), ("D", "G"),
]
graph = {}
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
for name in graph:
    graph[name] = sorted(graph[name])

dist = {"A": 0}
order = []
queue = deque(["A"])
while queue:
    v = queue.popleft()
    order.append(v)
    for nxt in graph[v]:
        if nxt not in dist:
            dist[nxt] = dist[v] + 1
            queue.append(nxt)
print("Order:", order)
for name in sorted(dist):
    print(name, "distance", dist[name])

Key points

  • Breadth-first search: a walk that explores one level at a time from the start
  • Level: the vertices at one distance from the start vertex
  • Distance: the number of edges on the path from the start to a vertex
  • A vertex is marked visited when it joins the queue, not when it leaves it
  • On an unweighted graph, the first path BFS finds to a vertex is a shortest path
  • Unweighted means every edge counts the same.

In this example, BFS starts at A with distance zero. A finds B and C, so both get distance one. B is served next and finds D and E at distance two. C then finds F, also at distance two. G is found last, from D, at distance three. The order line shows the levels leaving the queue in order. Each distance is the number of edges on a shortest path from A.

Note

BFS distances count edges, not weights.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In BFS, when is a vertex marked as visited?