Stack and Queue Traversal Within Time and Space Bounds

The pending-work structure determines the search

Imagine an unweighted graph describing possible connections among components. If you need the route with the fewest connections, it matters which candidate you inspect next. Breadth-first search (BFS) processes vertices in order of increasing distance from its starting vertex. A first-in, first-out queue maintains that order.

Watch the queue walkthrough before translating the idea into C. The examples use C++ and Java, but the invariant does not depend on either language.

The crucial choice is to mark a vertex when you enqueue it, not when you later remove it. A graph can contain a cycle, and two vertices can share a neighbor. Marking on enqueue prevents both from adding that neighbor to the queue. It also gives us a capacity guarantee: if there are $V$ vertices, no more than $V$ entries will ever be enqueued.

We’ll use this undirected graph, with vertices numbered 0 through 6:

• Vertex 0 connects to 1 and 2.
• Both 1 and 2 connect to 3; vertex 3 connects to 4.
• Vertices 5 and 6 connect to each other but not to vertex 0’s component.

Starting at 0, the queue first holds 1 and 2. Processing 1 discovers 3; processing 2 must not enqueue 3 again. Processing 3 then discovers 4. Thus vertex 4 is three edges from 0. Vertex 5 remains unreachable from 0.

Why is the first discovery of a vertex a shortest route by edge count? Initially the queue contains only the source, at distance zero. Processing a vertex at distance $d$ adds its undiscovered neighbors at distance $d+1$. Because the queue processes earlier additions first, it cannot process a longer route to a vertex before a shorter one. This guarantee is about unweighted hops, not lowest latency or cost when edges have different weights.

Implement BFS with a queue you can bound

The program below stores adjacency lists in two arrays. offset[u] and offset[u + 1] delimit vertex u’s neighbors in neighbor. This compact representation makes the work visible: processing a vertex scans only its actual neighbors, rather than testing every possible vertex.

bfs_hops must return the minimum hop count, or -1 when the destination is unreachable. It also fills dist and parent for every vertex reached from the source. An invalid argument returns -1 without modifying either output array. For a valid call, an unreached vertex retains -1 in both arrays.

Save this as traverse.c and replace only the two TODO regions. Spend roughly 3 minutes stating the queue invariant, 14 minutes implementing, and 5 minutes compiling and checking failures. The fixed-size arrays are deliberate: you should be able to explain why they cannot overflow.

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

enum { V = 7, ADJ_ENTRIES = 12 };

static const size_t offset[V + 1] = {
    0, 2, 4, 6, 9, 10, 11, 12
};

static const int neighbor[ADJ_ENTRIES] = {
    1, 2,       /* neighbors of 0 */
    0, 3,       /* neighbors of 1 */
    0, 3,       /* neighbors of 2 */
    1, 2, 4,    /* neighbors of 3 */
    3,          /* neighbors of 4 */
    6,          /* neighbors of 5 */
    5           /* neighbors of 6 */
};

static int bfs_hops(int src, int dst, int parent[V], int dist[V])
{
    if (src < 0 || src >= V || dst < 0 || dst >= V ||
        parent == NULL || dist == NULL)
        return -1;

    for (int v = 0; v < V; ++v) {
        parent[v] = -1;
        dist[v] = -1;
    }

    int queue[V];
    size_t head = 0;
    size_t tail = 0;

    /* TODO: Mark src discovered and enqueue it. */

    /* TODO: While the queue is nonempty, remove its next vertex.
       Scan that vertex's neighbors. Enqueue each undiscovered
       neighbor once, recording its distance and parent. */

    return dist[dst];
}

int main(void)
{
    int parent[V];
    int dist[V];

    assert(bfs_hops(0, 4, parent, dist) == 3);
    assert(parent[1] == 0);
    assert(parent[3] == 1);
    assert(parent[4] == 3);
    assert(dist[2] == 1);
    assert(dist[5] == -1);

    assert(bfs_hops(0, 5, parent, dist) == -1);
    assert(parent[5] == -1);
    assert(bfs_hops(5, 6, parent, dist) == 1);
    assert(bfs_hops(3, 3, parent, dist) == 0);
    assert(bfs_hops(-1, 4, parent, dist) == -1);

    puts("BFS tests passed");
    return 0;
}

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
  -fsanitize=address,undefined traverse.c -o traverse
./traverse

Here, head identifies the next entry to remove and tail the next unused slot. There is no need to wrap around to the beginning of the array: each vertex enters this queue at most once, so tail never exceeds V. The arrays represent a traversal of a fixed graph; for a general graph, you would size them to its vertex count.

Review the invariant and the bound

Compare your implementation with this replacement for the two TODO regions:

    dist[src] = 0;
    queue[tail++] = src;

    while (head < tail) {
        int u = queue[head++];

        for (size_t i = offset[u]; i < offset[u + 1]; ++i) {
            int v = neighbor[i];
            if (dist[v] != -1)
                continue;

            dist[v] = dist[u] + 1;
            parent[v] = u;
            queue[tail++] = v;
        }
    }

At the start of each loop iteration, the entries from head up to—but not including—tail are discovered vertices awaiting processing. Any vertex whose distance is not -1 has already been discovered, whether or not it has left the queue. That is why dist can serve as the visited marker.

For the call from 0 to 4, following parent backward from 4 gives 4, 3, 1, 0. Reversing that sequence yields a shortest-hop route. If the destination’s distance is -1, do not attempt to reconstruct a route. The parent of the source is also -1, but its distance is zero, so the distance distinguishes those cases.

Now account for the costs rather than memorizing them. Initializing the output arrays costs $O(V)$. Each vertex is enqueued and removed at most once, and across those removals each adjacency entry is scanned once. Therefore time is $O(V+E)$, where $E$ counts adjacency entries; an undirected edge appears twice here, which changes only a constant factor. The queue, dist, and parent each use $O(V)$ space, for $O(V)$ auxiliary space. The graph’s own adjacency storage is $O(V+E)$ and is not included in that auxiliary bound.

The representation matters. If you instead scanned a $V$-column adjacency-matrix row for every removed vertex, this implementation’s traversal bound would be $O(V^2)$, even for a sparse graph.

What changes with a stack?

A stack also holds pending vertices, but removes the most recently added one. That produces depth-first behavior rather than BFS’s distance-ordered frontier. The animation shows a stack managing pending work in a binary tree; its left/right order depends on the order in which children are pushed.

For a graph, you still need a visited marker because edges can lead back to vertices already discovered. The core iterative change to the C program would look like this, assuming valid src and dst:

static int reachable_dfs(int src, int dst)
{
    int seen[V] = {0};
    int stack[V];
    size_t top = 0;

    seen[src] = 1;
    stack[top++] = src;

    while (top > 0) {
        int u = stack[--top];
        if (u == dst)
            return 1;

        for (size_t i = offset[u]; i < offset[u + 1]; ++i) {
            int v = neighbor[i];
            if (!seen[v]) {
                seen[v] = 1;
                stack[top++] = v;
            }
        }
    }
    return 0;
}

Marking on push again ensures that no vertex occupies more than one stack slot. With these adjacency lists, DFS has the same $O(V+E)$ time and $O(V)$ auxiliary-space bounds as BFS. But those bounds do not imply the same answer: DFS can establish reachability, while the first route it finds need not use the fewest edges. If the problem asks for minimum unweighted hops, the queue is doing essential work.

Key takeaways

State the traversal contract before choosing the container. A queue processes the unweighted graph in increasing hop distance; a stack explores recently discovered work first. In either graph traversal, marking a vertex when it enters the container prevents duplicate pending entries and makes an $O(V)$ container capacity defensible. With adjacency lists, processing each vertex once and scanning each of its entries once gives $O(V+E)$ time.

Next you’ll apply traversal to binary trees. There, the absence of cycles simplifies visited-state handling, but the point at which you process a node—before, between, or after its subtrees—becomes central to the problem.