Discrete Mathsfor Engineers

Structures, proofs, and intuition
EN | PT

Breadth-First Search (BFS)

Part 1 — Graph Model & Problem Setting

Series: Breadth-First Search (BFS) Part 1 of 8
← Index Next →
Overview 1 2 3 4 5 6 7 8

Graph Model & Problem Setting

1. Why Start With the Model?

Before discussing algorithms, we must define precisely what problem we are solving.

Breadth-First Search is not just a traversal technique.
It is a graph-theoretic shortest-path algorithm for a specific mathematical structure.

So we begin with the object:

G = (V, E)

Where:

  • V = set of vertices
  • E ⊆ V × V = set of edges

This is the formal foundation used in Introduction to Algorithms.

2. Directed and Undirected Graphs

We distinguish two fundamental models.

Directed Graph (Digraph)
E ⊆ V × V

Edges have orientation: if (u, v) ∈ E, you may travel from u to v, but not necessarily from v to u.

Undirected Graph
E ⊆ {{u, v} ∣ u, v ∈ V}

Edges are symmetric: if u is adjacent to v, then v is adjacent to u.

BFS works for both models.

3. Graph Representation

An algorithm must operate on a data representation of G.

3.1 Adjacency List (Preferred)

Each vertex stores a list of its neighbors:

Adj[u] = { v ∈ V ∣ (u, v) ∈ E }

This is the standard representation in CLRS because it yields O(V + E) time complexity for BFS.

3.2 Adjacency Matrix

A matrix A ∈ {0, 1}|V|×|V|:

A[u, v] = { 1 if (u, v) ∈ E; 0 otherwise }

This representation leads to O(V2) time complexity for traversal.

For sparse graphs (common in engineering systems), adjacency lists are superior.

4. The Problem BFS Solves

Let s ∈ V be a distinguished source vertex.

We want to compute:

4.1 Reachability

Which vertices are reachable from s?

Reach(s) = { v ∈ V ∣ ∃ path from s to v }
4.2 Shortest Path Distance (Unweighted Graphs)

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

BFS computes d[v] = δ(s, v) for all reachable vertices.

Important: BFS does not minimize weights. It minimizes the number of edges. That is why it works only for unweighted graphs.

5. Paths — Formal Definition

A path of length k is a sequence v0, v1, …, vk such that (vi−1, vi) ∈ E for all i = 1, …, k.

The length of the path is k.

Shortest path problem: min k, subject to the existence of such a sequence.

6. Layer Structure — A Preview of BFS Geometry

Although we have not defined the algorithm yet, we introduce a structural idea.

Define distance layers:

Li = { v ∈ V ∣ δ(s, v) = i }
  • L0 = {s}
  • L1 = neighbors of s
  • L2 = vertices at distance 2
  • etc.

These layers partition the reachable subgraph. BFS will explore vertices exactly in this layered order.

This layered structure is the geometric heart of the algorithm.

7. The BFS Objective (Precise Statement)

Given a graph G = (V, E) and a source s ∈ V, compute:

  • The distance function d : V → N ∪ {∞}
  • A predecessor function π : V → V ∪ {NIL}

such that:

  • d[v] = δ(s, v)
  • The predecessor pointers form a shortest-path tree rooted at s

8. Why This Matters in Engineering

BFS appears in:

  • Network routing (unweighted hops)
  • Social network distance
  • Web crawling
  • Dependency resolution
  • Connectivity analysis
  • Bipartite testing

In discrete mathematics terms: BFS constructs the metric structure induced by edge-count distance.

This is not just traversal. It is the construction of a shortest-path metric space over G.

Next: Part 2 — The Core Idea (Layers + Queue)

Now that we introduced the problem and its motivation, we move to the central intuition. In Part 2, we explain how BFS explores the graph layer by layer, and why the queue (FIFO) structure is the key to this behavior.

Continue: Part 2 — The Core Idea (Layers + Queue) →
Made with ❤️ by Leandro Rodrigues