Visualizer CodeViz · Algorithms, visualized

Part II · Undirected graphs · week 1

Breadth-first search

Swap the recursion for a queue and vertices come off in order of distance. That single change turns any-path into shortest-path.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V + E)
findsshortest path (fewest edges)
queueFIFO — the whole difference
mark onenqueue, not dequeue

Reference: Sedgewick & Wayne, §4.1; Moore 1959.

Breadth-first search in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

from collections import deque

class BreadthFirstPaths:
    # DFS with a queue instead of recursion. Vertices leave the queue in
    # order of DISTANCE from s, so the first path found to any vertex is
    # the shortest one.

    def __init__(self, graph, s):
        self.marked = [False] * graph.V
        self.edge_to = [None] * graph.V
        self.dist_to = [float('inf')] * graph.V
        self._bfs(graph, s)

    def _bfs(self, graph, s):
        q = deque([s])
        self.marked[s] = True
        self.dist_to[s] = 0
        while q:
            v = q.popleft()               # closest unprocessed vertex
            for w in graph.adj(v):
                if not self.marked[w]:
                    self.edge_to[w] = v
                    self.dist_to[w] = self.dist_to[v] + 1
                    self.marked[w] = True  # mark on ENQUEUE, not dequeue
                    q.append(w)

Why it works

Why the queue gives shortest paths

The queue always holds vertices at distance d followed by vertices at distance d+1 — never anything further. So when v is dequeued, every vertex closer to s has already been processed, and any neighbour discovered now is at distance dist_to[v] + 1. That value is correct the first time it is written and never needs revising, which is why BFS finishes in one pass.

Mark on enqueue, not on dequeue

If you mark a vertex only when it comes off the queue, it can be enqueued many times before that happens — the queue can blow up to O(E) and vertices get processed repeatedly. Marking at enqueue time keeps each vertex in the queue at most once. This is the single most common BFS bug.

DFS and BFS are the same algorithm

Both maintain a set of discovered-but-unprocessed vertices and repeatedly take one out. DFS takes the most recently added (a stack), BFS the least recently added (a queue). Change the container, change the algorithm — and Part II's shortest-path and MST algorithms continue the pattern by taking the smallest one (a priority queue).

Where it is used

Fewest-edges routing, web crawling, Kevin Bacon / Erdős numbers, and as the augmenting-path finder inside Ford–Fulkerson (which is what makes it Edmonds–Karp). For weighted graphs, BFS is wrong and you need Dijkstra: fewest edges is not the same as shortest distance.

What to try in the animation

Each vertex's dist_to appears above it as soon as it is discovered — and it is never revised.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Breadth-first search in the player →

The rest of Undirected graphs