Graph Algorithms

How Breadth-First Search Works

Breadth-first search visits everything one hop away, then everything two hops away, using a queue. On an unweighted graph that makes the first path it finds the shortest one.

ABCDEFGH
In the queue
  1. A
Visit order

Nothing yet.

  • Not reached
  • Waiting
  • Current
  • Finished
Speed

Step 1 of 20

Start at A. Breadth-first keeps a queue, so nearer nodes come out first.

Counters

Visited
0/8
In the queue
1
Nodes
8
Edges
10

Settings

Graph

Breadth-first

  1. 1queue = [start]; seen = {start}
  2. 2while queue:
  3. 3 node = queue.shift()
  4. 4 for each neighbour:
  5. 5 if neighbour not in seen:
  6. 6 seen.add(neighbour)
  7. 7 queue.push(neighbour)

What each one answers

AlgorithmWhat it answersTimeNeeds
Breadth-firstFewest hops from the startO(V + E)A queue
Depth-firstReachability, one branch at a timeO(V + E)A stack
Cycle detectionDoes a cycle exist, and whereO(V + E)Node colours
Topological sortA valid order to do the work inO(V + E)No cycles
DijkstraCheapest path by edge weightO(E log V)Non-negative weights

V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.

Complexity

BestAverageWorstExtra memory
O(V + E)O(V + E)O(V + E)O(V)

Every vertex enters the queue once and every edge is examined once. The space is the queue plus the visited set, both bounded by V.

How breadth-first search works

Breadth-first search keeps a queue of vertices to explore. It takes one off the front, marks each unvisited neighbour as seen and pushes it onto the back, so the graph is explored in rings of increasing distance from the start. Because a vertex is reached for the first time on the shortest possible number of hops, recording each vertex's discoverer gives shortest paths on an unweighted graph for free.

  1. Mark the start as visited and put it in a queue.
  2. Take the vertex at the front of the queue.
  3. For each unvisited neighbour: mark it visited, record where it was reached from, and push it onto the back.
  4. Repeat until the queue is empty.
  5. Marking on enqueue, not on dequeue, is what stops a vertex being queued twice.

Implementation

The same algorithm the visualiser is running, written to be read.

from collections import deque


def bfs(graph, start):
    visited = {start}
    came_from = {start: None}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                # Marked on enqueue, not on dequeue: otherwise a vertex with
                # two discoverers gets queued twice.
                visited.add(neighbour)
                came_from[neighbour] = node
                queue.append(neighbour)

    return came_from

When to use it

  • Use it for shortest paths on unweighted graphs — social distance, fewest moves in a puzzle, shortest route on a grid.
  • Use it when the answer is probably close to the start: BFS finds it after exploring only the nearby part of the graph, where DFS might descend a long branch first.
  • Use it to find connected components, to test bipartiteness, and as the traversal inside maximum-flow algorithms.
  • Avoid it on graphs with weighted edges — fewest hops is not cheapest path, and that is Dijkstra's job.

Check yourself

If the animation made sense, these should too.

Why does BFS find the shortest path on an unweighted graph?

Because it explores in rings of increasing distance: everything one hop away is visited before anything two hops away. A vertex is therefore first reached by a path of the fewest possible hops, and that first path is the shortest.

Why mark a vertex visited when it is enqueued rather than when it is dequeued?

Because a vertex can be a neighbour of several vertices already in the queue. Marking on dequeue lets it be enqueued once per discoverer, which duplicates work and, on a dense graph, can blow the queue up badly.

More graph algorithms