Discrete Mathsfor Engineers

The Core Idea of BFS

Before writing code, we must understand the geometry of the algorithm.

Breadth-First Search is not simply visiting neighbors.

It is the systematic exploration of a graph in distance layers.

BFS expands outward from a source vertex like a wave.

Distance Layers

Let G = (V, E) and let s ∈ V be a source vertex.

Define the distance function δ(s, v) as the minimum number of edges in any path from s to v.

Now define the layers:

These sets partition the reachable vertices:

• L₀ = {s}
• L₁ = neighbors of s
• L₂ = vertices at distance 2
• L₃, and so on

This layered structure is the geometric heart of BFS.

Why Layers Matter

BFS guarantees: if a vertex is discovered in layer L_i, then no shorter path to that vertex exists.

Why?

Because BFS explores all vertices at distance i before exploring any vertex at distance i + 1.

This is not accidental. It is enforced by the queue.

The Queue Discipline

BFS uses a queue.

Queue = First In, First Out (FIFO).

• Vertices are enqueued when discovered.
• Vertices are dequeued in the same order they were inserted.

This simple rule forces the algorithm to respect layers.

The Wavefront Interpretation

Think of BFS as a wave expanding from s.

At step i:

• All vertices in L_i are processed.
• Their undiscovered neighbors become L_i+1.

The frontier between explored and unexplored vertices is called the wavefront.

This interpretation explains both correctness and optimality.

Engineering Interpretation

Why this works:

• Edges all have equal weight (unweighted graph).
• Distance is measured by edge count.
• FIFO ordering preserves shortest distance first.

Therefore:

for every reachable vertex v.

Conceptual Summary

The essence of BFS:

It is not traversal by chance. It is traversal by metric structure.