Discrete Mathsfor Engineers

3. The Algorithm

In this section, we formalize Breadth-First Search (BFS) using the classical presentation from Introduction to Algorithms (CLRS).

We move from intuition to structure: precise state, precise steps, and the guarantees that follow.

3.1 Objective

Given a graph G and a source vertex s, BFS explores the graph in increasing distance from s.

In unweighted graphs, this means BFS computes shortest-path distances (by number of edges) from s to every reachable vertex.

3.2 Formal Model

Let:

• G = (V, E) be a graph
• s ∈ V be the source vertex

3.3 Vertex State

Each vertex v ∈ V stores:

• color[v] → WHITE, GRAY, BLACK
• d[v] → distance from the source
• π[v] → predecessor

This coloring enforces structure and prevents revisiting vertices.

3.4 CLRS Pseudocode — BFS

BFS(G, s):

    for each vertex u in V[G]:
        color[u] = WHITE
        d[u] = ∞
        π[u] = NIL

    color[s] = GRAY
    d[s] = 0
    π[s] = NIL

    Q = empty queue
    ENQUEUE(Q, s)

    while Q is not empty:
        u = DEQUEUE(Q)

        for each v in Adj[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = d[u] + 1
                π[v] = u
                ENQUEUE(Q, v)

        color[u] = BLACK

3.5 Structural Guarantees

The algorithm guarantees:

1. Vertices are explored in increasing distance order.
2. The first time we reach a vertex, we have found a shortest path (in unweighted graphs).
3. The predecessor pointers π[v] form a BFS tree.

3.6 Why This Produces a Tree

Every vertex (except the source) receives exactly one predecessor.

Therefore:

• The predecessor relation defines a tree.
• If n vertices are reachable, the BFS tree has exactly n − 1 edges.

3.7 Time Complexity

If adjacency lists are used:

Each vertex is enqueued at most once. Each edge is examined at most twice (undirected case).