Programming

Breadth-First Search

It is not a graph traversal. It is an unweighted shockwave detonating from a single spark: expanding in concentric spheres of integer distance, carving out the exact geodesic metric of the graph one frontier at a time.

DFS circles the rim in 4 hops; expand in concentric ripples to hit the 3-hop chord.

Mission 03about 9 min

Propagate concentric distance rings through unweighted graphs to lock in shortest paths and certify 2-colourability.

  1. Step the FIFO queue to observe wavefronts expand level by level
  2. Identify the chord edge that undercuts perimeter traversals
  3. Test level parity to expose odd cycles that destroy bipartiteness

After thisYou can compute unweighted geodesics and cycle parities in linear time using a single monotone queue.

Short on timeThe GraphCanvas wavefront explorer in §2

Concentric Rings of Integer Distance

3 minthe hook

On the network below, G sits three hops from the source S, not four. The chord C–G cuts the corner, and every route that hugs the outside of the drawing pays an extra hop for the privilege.

That is the trap. Follow one path to the end and call the first arrival shortest: the route through E can reach G first, four hops out, and nothing in that traversal revises the number.

The picture is the rings: the level sets around S. The graph fixes them, and the order the queue visits them does not.

The rightmost vertex G terminates two prominent perimeter chains that are each 4 hops from S. At what depth does the expanding BFS wave actually swallow vertex G?

1 / 28
breadth-first search · source S
SABCDEFG

1/28 start at S: enqueue it

queueS
  1. 1 start at S: enqueue it

Eight vertices, source S. Step, or press play. Green edges are the tree the search accepts; red edges are the ones it refuses. The chip row under the log is the queue, read left to right.

Watch the queue order scramble while the ring number stays fixed. The level of a vertex is the invariant; its position in the queue is not.

NextWhy does depth-first traversal take four hops where concentric rings find three?

The Tour vs. The Level Metric

2 minthe trap

Textbooks commonly teach breadth-first search as a simple recipe: insert the source into a FIFO queue, pop the front, and enqueue unvisited neighbours. That procedural description conceals the true mathematical object.

The specific order in which vertices emerge from the queue is an arbitrary artefact of tie-breaking and neighbour indexing. What remains absolutely fixed across every valid run is the integer label assigned to each vertex.

Read the canvas as computing an exact metric tensor rather than a traversal tour. Source receives 0, while subsequent vertices receive their geodesic hop distance from the spark.

NextHow does the geodesic distance metric reach a unique fixed point?

The Geodesic Metric and its Fixed Point

2 minthe invariant

Fix source . The distance is the minimum number of edges on any path from to . The level set partitions reachable vertices into concentric metric spheres.

Every edge in the graph must obey the Lipschitz triangle inequality:

This inequality yields Bellman’s equation for unweighted graphs, where denotes the neighbourhood of :

The distance function is the least fixed point of this equation. On the canvas, vertex connects to neighbours at levels 3, 3, and 2, uniquely fixing its distance at .

NextHow does the monotone queue guarantee König's bipartite parity property?

The Monotone Queue and König’s Parity Theorem

2 minthe algebra

The two-level queue invariant. If the vertex at the front of the queue has level , then every vertex currently waiting in the queue has level or .

Because each unweighted edge has length 1, exploring a level- vertex discovers only neighbours at level . The queue remains permanently sorted by distance without requiring any comparison logic.

Dijkstra requires an expensive priority queue to extract the nearest vertex. Why can BFS extract the minimum using a basic FIFO queue?

Shortest-path trees and parity. Tree edges form a directed tree where every child sits at depth . Non-tree edges can only connect vertices whose levels differ by 0 or 1.

A graph is bipartite if and only if no edge connects two vertices at the identical level. If an edge joins two vertices at level , tracing their ancestors back to their lowest common ancestor at level produces an odd cycle of length .

This constructive observation proves König’s theorem (1936): a graph is 2-colourable if and only if it contains no odd cycle. BFS validates bipartiteness in a single linear pass.

NextWhat structural chord breaks bipartiteness and produces an odd cycle?

The Chord That Kills Bipartiteness

2 minthe simulation

Here are the same eight vertices with chords C–D and C–G removed, leaving an 8-vertex cycle S–A–C–E–G–F–D–B–S.

1 / 26
breadth-first search · source S
SABCDEFG

1/26 start at S: enqueue it

queueS
  1. 1 start at S: enqueue it

The same eight vertices as a single even cycle. BFS still refuses one edge, F–G, but here it joins level 3 to level 4 — check the log. No edge joins two equal levels, so the parity colouring is a real 2-colouring: even levels one colour, odd levels the other.

On the pure cycle, the levels partition cleanly into even and odd rings. Reinserting a single chord can instantly introduce an odd cycle.

1 minboss round

Removing chords C–D and C–G leaves an 8-vertex cycle. If you reinsert chord C–G, does the graph remain bipartite?

NextWhat memory explosion threatens wide wavefronts in small-world graphs?

Metric Geodesics and Small-World Clocks

2 minsystems

BFS computes the exact geodesic metric of an unweighted graph in time. Rerunning BFS from each vertex computes the complete graph diameter and all-pairs hop counts.

In distributed computing, each BFS level corresponds to one broadcast round or MapReduce pass (Cohen 2009). The eccentricity of a node becomes the physical latency clock of the network.

In social networks, Milgram (1967) demonstrated the ‘six degrees of separation’ phenomenon: human connection graphs exhibit remarkably small diameters despite having billions of nodes.

NextWhat structural invariant governs the next chapter?

The Geometry of the Wavefront: Memory Bounds

2 minfrontier

The queue stores the frontier, which spans at most two adjacent levels. Its peak size is determined by the maximum level width of the network rather than total vertices.

The chart below shows level sizes across three canonical topologies: a linear path, a 2D square grid, and a radial star graph.

How wide is one level? The frontier you have to hold.

0510152005101520depth from the sourcevertices in the level
path, 21 verticessquare grid, 11 by 11star, 21 vertices

The path frontier requires only 1 vertex in memory. The square grid expands diamond-like to 11 vertices before shrinking, while the star graph demands storing all 20 leaves in a single burst.

The resulting BFS tree is one witness among many. While tie-breaking produces different tree pointers, the underlying metric distances are absolute invariants.

Next missionBellman–FordDijkstra freezes T at 12; relax all edges across 4 rounds to uncover the -11 siphon.

Attributions

  • Moore 1959 — E. F. Moore, The shortest path through a maze: the breadth-first sweep that labels every vertex with its distance from one source.
  • Lee 1961 — C. Y. Lee, An algorithm for path connections and its applications: the same search as wire routing, where each level is a wavefront.
  • König 1936 — D. Kőnig, Theorie der endlichen und unendlichen Graphen: a graph is bipartite if and only if it has no odd cycle; BFS proves the half that is not immediate.
  • Milgram 1967 — The small world problem: the measured handful of hops that makes the level count a social fact.
  • Cohen 2009 — Graph twiddling in a MapReduce world: one breadth-first level per round, so the round count is the eccentricity of the source.
  • Dijkstra 1959 — the weighted version, where the sortedness argument fails and the queue must become a priority queue.