Breadth-first search: queue and unweighted distances

From neighbors to layers

Read “Graph terms and adjacency representations” (graph-terms-and-adjacency-representations) and “Queues: FIFO and bounded circular array” (queues-fifo-and-bounded-circular-array) first. You need vertices, edges, adjacency matrices, valid array indices and FIFO enqueue/dequeue. This lesson explains how those ideas find every vertex reachable from one source, in increasing shortest-path edge count. We use a simple undirected, unweighted graph with vertices 0 through n−1. A 1 in a[u][v] means one edge; 0 means no edge. The matrix is symmetric and its diagonal is zero.

Imagine passing a message through a network: your direct contacts form the first wave, their not-yet-contacted contacts the second wave, and so on. A FIFO waiting line processes an earlier wave before a later one. Each person is marked when first added to the line, so two contacts cannot add that person twice. This analogy concerns number of links; it does not model travel time, message delays or edge costs.

Breadth-first search (BFS) discovers the source at distance 0, then vertices at distance 1, then 2, and so forth. Discovery means assigning a distance and inserting into the queue. Processing means removing a vertex and scanning its neighbors. A discovered vertex may still be waiting. Our printed order is the processing order. Because each vertex is inserted once into a FIFO queue, this is also the discovery order here.

The rule, with one marker doing two jobs

Initialize dist[v] = −1 for every vertex. This means “not discovered yet”; after a successful search finishes, it means “unreachable from this source.” Set dist[source] = 0 and enqueue the source. While the queue is nonempty:

1. Dequeue u from the front.
2. Scan v = 0, 1, …, n−1, in that order.
3. If a[u][v] == 1 and dist[v] == −1, set dist[v] = dist[u] + 1, then enqueue v.

The distance array is also the visited/discovered marker. Mark before enqueueing, not when eventually dequeuing. Otherwise two already-queued parents can both insert their shared neighbor before that neighbor is processed. Cycles are harmless under our rule: the source is already marked, and every other vertex is marked on its first insertion.

Ascending neighbor order makes traces reproducible. It resolves ties within the same distance layer; it does not imply that the entire output is sorted by vertex number. A different neighbor order can change processing order and the selected discovery parent, but not shortest distances.

Why these distances are shortest

The source has a zero-edge path to itself. Whenever u discovers v, appending edge u−v to the discovered path to u gives a path of length dist[u] + 1. So each assigned distance has an actual path behind it.

FIFO order processes complete earlier layers before later layers. While processing layer d, any new discovery enters at the back with distance d+1; already-waiting layer-d vertices stay ahead of it. Suppose v first gets distance d+1 but a shorter path existed. Its predecessor on that shorter path would have been processed in an earlier layer and would already have discovered v, a contradiction. Thus the first assigned distance is final.

These are shortest paths by number of edges in an unweighted graph (equivalently, edges all have one common positive cost). They are not a minimum-total-weight guarantee for unequal weights. A one-edge route of weight 100 can cost more than a two-edge route with weights 1 and 1; BFS still favors the one-edge route by edge count. Our 0/1 matrix stores absence/presence, not weights.

The current validator deliberately accepts only undirected graphs. For a directed adaptation, follow outgoing arcs a[u][v]=1 and remove the symmetry requirement. A directed single-source search still finds shortest unweighted directed-path distances, but its reachable set is not generally a connected component. Repeated roots with shared visited markers produce a traversal forest dependent on root order; do not label its trees as weakly or strongly connected components. Those directed component algorithms are outside this lesson.

Storage and validity contract

The C11 program uses CAP = 6 and no dynamic allocation. Graph contains n and a CAP×CAP integer array. BfsResult contains distance and processing-order arrays and count. The caller supplies a live, fully initialized Graph and separate live writable BfsResult storage, with no overlap. Null, dangling or undersized pointers are outside this contract; the validator cannot repair storage that does not exist. The output fields need not be initialized by the caller because bfs initializes all of them before checking input.

Active vertices are 0 through n−1, with 0 ≤ n ≤ CAP. valid_graph checks n first, then all active entries for 0/1 values, symmetry and zero diagonal. Inactive rows/columns do not represent vertices. A graph with n=0 is structurally valid, but there is no valid source, so bfs returns 0 for it. Invalid graph or source also returns 0, with count=0 and every output slot reset to −1. Always check this status: failed validation is not a successful search reporting unreachable vertices.

On success, bfs returns 1. Only order[0] through order[count−1] form the processing sequence, and only dist[0] through dist[n−1] refer to active vertices. The graph must remain unchanged during the call. All calls here are sequential.

The local queue array has CAP physical slots; this search uses at most n of them in total. head is the index of the next item to remove; tail is the next free insertion position. The waiting queue is queue[head..tail−1], and head == tail means empty. queue[tail++] writes at the old tail and then increments it; queue[head++] reads at the old head and increments it.

Because each active vertex is inserted at most once, 0 ≤ head ≤ tail ≤ n ≤ CAP. Before an insertion of a new vertex, fewer than n vertices have been inserted, so the write is in bounds. Indices never wrap and removed slots are not reused. This is a one-search bounded queue, not a generic reusable queue for unlimited enqueue/dequeue operations. A fresh call creates a fresh queue; a general long-lived bounded queue needs a reuse strategy such as the circular-array queue from the prerequisite. Distances cannot exceed n−1 ≤ 5, so the addition is bounded too.

Worked trace 1: a diamond, a cycle and an unreachable vertex

Use n=6 and undirected edges {0−1, 0−2, 1−3, 2−3, 3−4}. Vertex 5 is isolated. Start at 0. The diamond 0−1−3−2−0 is a cycle. In the queue snapshots, only waiting items are shown; removed items may remain physically in array slots.

Processing order is 0,1,2,3,4; distances in vertex-index order are [0,1,1,2,3,−1]. Both 0−1−3 and 0−2−3 are shortest paths to 3, each with two edges. Vertex 1 discovers 3 first only because of the stated scan order. The edge from 2 to 3 does not enqueue 3 again. Vertex 5 is never enqueued.

Complete C11 program

New C syntax: typedef struct groups named fields into a record type and gives it a short name, such as Graph or BfsResult. In Graph g = {6, {...}}, the first initializer sets n; the inner braces initialize the matrix one row at a time. &g and &result supply the addresses of the existing records to bfs; the function can read the graph and fill the caller’s result through those addresses. int queue[CAP] = {0} initializes every queue slot to zero, although only inserted slots are read. BfsResult result has no initializer in main, but bfs writes count and every dist/order slot before any result value is read, even on failure.

The struct wrapper lets a const Graph pointer expose a read-only graph without a multidimensional-array qualifier mismatch in strict C11. g->n selects a field through a pointer; out->dist[v] writes the caller's result. The queue and counters are local to each call.

#include <stdio.h>

enum { CAP = 6 };
typedef struct {
    int n;
    int a[CAP][CAP];
} Graph;
typedef struct {
    int dist[CAP];
    int order[CAP];
    int count;
} BfsResult;

/* g points to one live, fully initialized Graph. */
int valid_graph(const Graph *g) {
    if (g->n < 0 || g->n > CAP) {
        return 0;
    }
    for (int u = 0; u < g->n; ++u) {
        for (int v = 0; v < g->n; ++v) {
            if ((g->a[u][v] != 0 && g->a[u][v] != 1) ||
                g->a[u][v] != g->a[v][u] ||
                (u == v && g->a[u][v] != 0)) {
                return 0;
            }
        }
    }
    return 1;
}

/* out points to separate live writable storage, disjoint from g. */
int bfs(const Graph *g, int source, BfsResult *out) {
    out->count = 0;
    for (int v = 0; v < CAP; ++v) {
        out->dist[v] = -1;
        out->order[v] = -1;
    }
    if (!valid_graph(g) || source < 0 || source >= g->n) {
        return 0;
    }
    int queue[CAP] = {0};
    int head = 0;
    int tail = 0;
    out->dist[source] = 0;
    queue[tail++] = source;
    while (head < tail) {
        int u = queue[head++];
        out->order[out->count++] = u;
        for (int v = 0; v < g->n; ++v) {
            if (g->a[u][v] == 1 && out->dist[v] == -1) {
                out->dist[v] = out->dist[u] + 1;
                queue[tail++] = v;
            }
        }
    }
    return 1;
}

int main(void) {
    Graph g = {6, {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {0, 1, 1, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    BfsResult result;
    if (!bfs(&g, 0, &result)) {
        puts("Invalid graph or source");
        return 1;
    }
    printf("Order:");
    for (int i = 0; i < result.count; ++i) {
        printf(" %d", result.order[i]);
    }
    printf("\nDistance:");
    for (int v = 0; v < g.n; ++v) {
        printf(" %d", result.dist[v]);
    }
    putchar('\n');
    return 0;
}

Expected output:

Order: 0 1 2 3 4 Distance: 0 1 1 2 3 -1

Worked trace 2: ascending neighbors do not globally sort the output

Take n=6 and edges {0−2, 0−4, 2−5, 4−1}, with isolated vertex 3. Source 0 gives [0] initially. Removing 0 gives queue [2,4], both at distance 1. Removing 2 appends 5: [4,5]. Removing 4 appends 1: [5,1]. Removing 5 and then 1 empties the queue. The order is 0,2,4,5,1, and the distance array is [0,2,1,−1,1,2]. Vertex 5 is processed before vertex 1 because its parent entered earlier. FIFO preserves layers, not numerical sorting.

Worked trace 3: an isolated source and disconnected coverage

Take n=5 and edges {0−1, 1−2, 3−4}. A search from 0 processes 0,1,2 and returns [0,1,2,−1,−1]. A fresh search from 3 processes 3,4 and returns [−1,−1,−1,0,1]. These are two different distance arrays for two different sources. In the first six-vertex example, a fresh search from isolated source 5 processes only 5 and returns [−1,−1,−1,−1,−1,0]. A valid singleton similarly processes its sole source at distance 0. An empty graph cannot supply a source.

To traverse all components of an undirected graph, an outer loop can choose each still-unvisited vertex as a new root and run a queue traversal with a visited array shared across that whole outer loop. This constructs a BFS forest. Each root has its own component-relative distance 0; those distances are not distances from one common source. The provided bfs is single-source and resets its output on every call. Calling it repeatedly and keeping only the last result does not accumulate a forest. No all-components routine is implemented here.

Cost, mistakes and a key idea box

For r vertices reachable from the source, the BFS loop scans n entries in each of r rows: O(nr), worst-case O(n²). This program also validates the entire active n×n matrix, so the full call is O(n²) for nonempty input. Matrix storage is O(n²); working queue and result arrays are O(n) in the scalable version. Here CAP is fixed at 6, so actual allocated sizes have fixed bounds. The familiar O(V+E) BFS bound uses adjacency lists; it is not the row-scanning bound for this matrix program. The exhaustive author tests use a separate reference algorithm; that algorithm is not part of the learner's BFS.

Common errors: marking on dequeue; re-enqueueing an already discovered vertex; assigning distance from vertex labels; reporting a disconnected vertex at distance 0; treating enqueue and processing as the same instant; ignoring a failure status; claiming weighted optimality; or claiming the output is numerically sorted.

Key idea box:

• FIFO processes vertices in nondecreasing shortest-path edge count.
• Set the discovery marker before insertion; each vertex enters at most once.
• dist[source]=0; after success, dist[v]=−1 exactly when v is unreachable from that source.
• Neighbor order chooses among same-layer ties without changing distances.
• Single-source reachability and whole-graph component coverage answer different questions.

Two extra exercises with worked checks

1. Reverse the neighbor scan in trace 1 to v=n−1 down to 0. Predict the order and distances before editing code. Answer: 0,2,1,3,4; distances remain [0,1,1,2,3,−1]. Vertex 2 now discovers 3 first. The two-edge shortest distance to 3 does not change.
2. Add undirected edge 0−4 to trace 1, keeping ascending scan order. Predict the queue just after processing 0 and then all distances. Answer: queue [1,2,4]; order 0,1,2,4,3; distances [0,1,1,2,1,−1]. Vertex 1 discovers 3 at distance 2; when 4 is processed, 3 is already marked. A shortcut changes distances, while the isolated vertex remains unreachable.

The six questions accompanying this lesson are original foundation practice, each with exactly one correct option. They do not claim to be past exam questions or a complete exam syllabus.

Original practice questions

B01

An undirected graph has vertices 0..4 and edges {0–2, 0–3, 2–4, 3–1}. BFS starts at 0 and scans neighbors in ascending order. What is the processing order?

A. 0, 1, 2, 3, 4 B. 0, 2, 4, 3, 1 C. 0, 2, 3, 4, 1 D. 0, 3, 2, 1, 4

Answer: C

A is incorrect: ascending neighbor scans do not globally sort the processing order; 1 is two edges away. B is incorrect: queued vertex 3 must be processed before newly inserted vertex 4. C is correct: 0 inserts 2,3; 2 appends 4; 3 appends 1, giving 0,2,3,4,1. D is incorrect: the scan from 0 inserts 2 before 3, not the reverse.

B02

For n=6, undirected edges are {0–1, 1–2, 2–3, 0–3, 4–5}. After a successful BFS from 0, what is dist[0..5]?

A. [0,1,2,1,−1,−1] B. [0,1,2,3,−1,−1] C. [0,1,2,1,0,1] D. [1,2,3,2,−1,−1]

Answer: A

A is correct: 1 and 3 are adjacent to 0, 2 is two edges away, and component {4,5} is unreachable. B is incorrect: direct edge 0–3 makes dist[3]=1, even though a three-edge route also exists. C is incorrect: this mixes distances from a second root 4 into a single-source result. D is incorrect: distance counts edges, so the source has distance 0, not 1.

B03

Why does this implementation assign dist[v] before enqueueing v?

A. To sort the queue numerically B. To permit the same vertex to enter once per incoming edge C. To ensure every graph vertex is reachable D. To prevent another processed neighbor from enqueueing v again

Answer: D

A is incorrect: FIFO insertion does not sort vertex labels. B is incorrect: the purpose is one insertion per vertex, not one per edge. C is incorrect: markers do not add missing paths between components. D is correct: dist[v] ceases to be −1 immediately, including while v is still waiting in the queue.

B04

For a valid graph with n vertices, why is the monotonic queue safe without wrapping its indices?

A. Dequeue resets tail to zero every time B. At most n total insertions occur in one call C. The queue never contains more than two vertices D. An adjacency matrix dynamically expands the queue

Answer: B

A is incorrect: both head and tail only increase during this search. B is correct: source and every other vertex are inserted at most once, so the next write never needs a slot beyond n−1. C is incorrect: in a star, processing the center can leave n−1 vertices waiting. D is incorrect: queue storage is the fixed local array; the matrix does not change its capacity.

B05

Which claim is justified for this matrix-based, validated BFS implementation?

A. The full call always takes O(V+E) because it is BFS B. It minimizes total cost for arbitrary positive edge weights C. It gives shortest edge-count distances; the full nonempty call is O(n²) D. It visits every component from any valid source

Answer: C

A is incorrect: matrix row scans and full matrix validation do not have the adjacency-list bound. B is incorrect: unequal weights can make a path with fewer edges more costly. C is correct: FIFO establishes unweighted distances, and full active-matrix validation scans n² entries. D is incorrect: a single source reaches only its own component in an undirected graph.

B06

A fully initialized Graph has n=0 and a zero matrix. With valid separate result storage, what does bfs(&g, 0, &result) do?

A. Returns 1 and processes vertex 0 B. Returns 0, sets count=0, and resets all result slots to −1 C. Returns 1 with dist[0]=−1 because 0 is unreachable D. Reads matrix row 0 before checking the source

Answer: B

A is incorrect: with n=0 there is no active vertex 0. B is correct: the empty graph passes structural validation but source 0 fails the source-range check; output initialization occurs first. C is incorrect: unreachable active vertices are a successful-search concept; here there is no valid source and the status is 0. D is incorrect: the validator has no active entries to scan and the source check rejects the call before traversal.