13. Graph Traversal

What a Traversal Must Remember#

A traversal systematically explores vertices by following graph edges. Unlike a list traversal, it cannot just follow a next pointer until NULL: a vertex may have several neighbours, several routes may lead to the same vertex, and a cycle can keep bringing us back to it.

We therefore maintain a record of discovery, meaning that a vertex has been found and scheduled, and exploration, meaning that we are examining its neighbours. Lectures often call both “visited”; pay attention to the actual point where the flag changes. A frontier stores vertices waiting to be explored. Its discipline determines which route we follow next.

Breadth-first search (BFS) uses a FIFO queue, exploring older discoveries first. Depth-first search (DFS) uses recursion or a stack, pursuing one branch before returning to the alternatives. Recall the queue and stack operations from 08. Abstract Data Types and the call stack from 02. Recursion.

The numbers in the image are discovery positions, not edge weights or vertex names. Starting at a and prioritising smaller letters, BFS discovers a,b,c,d,e,g,i,f,h; DFS discovers a,b,c,d,i,g,f,e,h. Both reach the same vertices, but their discovery trees differ.

The input graph alone does not determine a unique traversal order. State the starting vertex, neighbour order, and traversal variant before predicting a sequence. The players below keep neighbours in the order of the authored edge list. For our numeric examples, that list makes each vertex's neighbour order ascending.

Breadth-First Search#

The Queue and Discovery Rule#

Input: a graph and source vertex src. Output: all vertices reachable from src, optionally a predecessor for each one. For now edges are unweighted, or every edge has equal cost.

1. Initialise visited to false, pred to -1, and an empty queue.
2. Mark the source discovered and enqueue it.
3. Dequeue the oldest waiting vertex $v$.
4. For each undiscovered neighbour $w$, mark it, record pred[w] = v, and enqueue it.
5. Repeat until the queue is empty.

The predecessor of $w$ is the vertex from which we first reached it. Following predecessor links backwards reconstructs the route. Discovery happens when enqueuing, so two explored vertices cannot schedule the same neighbour twice. “Not yet dequeued” does not mean “not yet discovered”.

A Small Worked Trace#

Use vertices 0–6 and edges $0\! -\!1$, $0\! -\!2$, $1\! -\!3$, $1\! -\!4$, $2\! -\!4$, $3\! -\!5$, $4\! -\!5$. Vertex 6 is isolated. Queue entries are shown from front to rear.

Watch vertex 4: it is discovered from 1 while 2 is still queued. Exploring 2 must leave its predecessor unchanged. Vertex 6 remains undiscovered because there is no route to it.

The player records exploration order 0,1,2,3,4,5; discovery order agrees here, because each queued vertex is eventually explored. Its counters record selected teaching operations, rather than all matrix checks in a C implementation.

Practice. Just after exploring 1, can 4 be enqueued again when exploring 2? What shortest path to 5 has the traversal recorded?

Why BFS Finds Fewest-Edge Paths#

The source forms distance layer 0. Its neighbours form layer 1. When we dequeue a layer-1 vertex, any newly discovered neighbour has a route of length 2. FIFO order ensures that all layer-1 vertices are explored before those newly enqueued layer-2 vertices. The same reasoning repeats at each layer.

Thus vertices are discovered in nondecreasing distance from the source. If $w$ first appears from a vertex in layer $d$, the recorded route has length $d+1$. A shorter route would have reached it from an earlier layer, which has already been explored. That contradicts $w$ still being undiscovered.

This is a correctness argument using an invariant: a fact that remains true as the loop repeats. Here, the queue contains discovered vertices in distance-layer order. Neighbour ordering may choose among several equally short routes, but cannot make the first recorded route longer.

BFS minimises the number of edges. A direct edge costing 100 is one hop, while two edges costing 1 each are two hops. BFS prefers the direct edge even though its weighted cost is worse. Use 15. Directed Graph Algorithms and Shortest Paths for unequal edge weights.

The Lecture Path Example#

The source 0 discovers 1, 2 and 5. Exploring 5 discovers 4, 6 and 7. Exploring 4 then discovers 8. Therefore pred[8]=4, pred[4]=5, and pred[5]=0. Read the chain backwards as $8\leftarrow4\leftarrow5\leftarrow0$. The forward shortest path is $0\to5\to4\to8$, length 3.

The lecture shows pred[0]=-1 when a separate visited array is used. If the predecessor array replaces that array, initialise pred[src]=src; otherwise a neighbour can mistake the source for an undiscovered vertex. The self-predecessor is a sentinel, not a graph loop.

Implementing BFS in C#

The next code works with the matrix Graph defined in 12. Graphs and Representations. Put it in the same implementation file, or adapt adjacency access through the ADT. The caller supplies pred and dist arrays of at least g->nV elements; the function fills them and owns only its temporary queue.

void bfs(Graph g, Vertex src, int pred[], int dist[]) {
    checkVertex(g, src);
    int *queue = checkedCalloc((size_t)g->nV, sizeof *queue);
    int front = 0, rear = 0;
    for (int v = 0; v < g->nV; v++) {
        pred[v] = -1;
        dist[v] = -1;     // unreachable until discovered
    }
    pred[src] = src;
    dist[src] = 0;
    queue[rear++] = src;
    while (front < rear) {
        int v = queue[front++];
        for (int w = 0; w < g->nV; w++) {
            if (g->edges[v][w] && pred[w] == -1) {
                pred[w] = v;
                dist[w] = dist[v] + 1;
                queue[rear++] = w;
            }
        }
    }
    free(queue);
}

// Returns forward path length in vertices; 0 means unreachable.
// out must have space for g->nV vertices; pred must come from src.
int recoverPath(Graph g, Vertex src, Vertex dest,
                const int pred[], int out[]) {
    checkVertex(g, src); checkVertex(g, dest);
    if (pred[dest] == -1) return 0;
    int len = 0;
    for (int v = dest; ; v = pred[v]) {
        assert(len < g->nV); // a valid predecessor chain cannot cycle
        out[len++] = v;
        if (v == src) break;
        assert(pred[v] >= 0 && pred[v] < g->nV);
    }
    for (int i = 0; i < len / 2; i++) {
        int tmp = out[i]; out[i] = out[len - 1 - i];
        out[len - 1 - i] = tmp;
    }
    return len;
}

Each vertex is enqueued at most once, so capacity $V$ suffices. front and rear only increase: this one traversal does not need a general circular queue because it schedules at most $V$ items in total. dist stores hop count; an output path with len vertices has len-1 edges.

If src == dest, recovery returns the one-vertex route [src], representing the zero-edge path. For an unreachable destination, do not follow pred[dest] == -1 as an array index. You can stop BFS once the destination is discovered if you only need that route; a full run is required to populate all reachable distances.

Practice. What happens if pred[src] remains -1 and the graph contains $0-1$ with source 0?

Recursive Depth-First Search#

DFS marks the current vertex, then recursively explores an undiscovered neighbour before continuing with the next neighbour. Each recursive call remembers where its neighbour loop paused. When that branch has no new neighbour, returning to the caller resumes the previous loop: this is backtracking.

On the earlier seven-vertex graph, DFS with ascending neighbours begins $0\to1\to3\to5\to4\to2$. At 2 both neighbours are already discovered, so it returns to 4; then to 5, 3, 1, and finally 0. Vertex 0's other neighbour 2 is now discovered, so no second recursion starts there.

Watch the recursion frontier return through callers after the dead end at 2. This built-in models recursive DFS, matching this section. Its stack is a call path, not the pending-vertex stack used by the later iterative variant.

The lecture graph's ascending-neighbour order is 0,1,5,3,2,4,7,8,9,6. At 5, the branch through 3 is completely processed before neighbour 6 is considered. That explains why 6 appears last despite being close to the source.

Finding a Path with DFS#

The same predecessor idea works, but DFS's first route need not be shortest. A helper can return immediately on reaching the destination. A true result passes back through its callers; a false result lets the caller try its next neighbour.

static bool dfsPathRec(Graph g, Vertex v, Vertex dest, int pred[]) {
    if (v == dest) return true;
    for (int w = 0; w < g->nV; w++) {
        if (g->edges[v][w] && pred[w] == -1) {
            pred[w] = v;
            if (dfsPathRec(g, w, dest, pred)) return true;
        }
    }
    return false;
}

bool dfsFindPath(Graph g, Vertex src, Vertex dest, int pred[]) {
    checkVertex(g, src); checkVertex(g, dest);
    for (int v = 0; v < g->nV; v++) pred[v] = -1;
    pred[src] = src;
    return dfsPathRec(g, src, dest, pred);
}

Because the predecessor is set before calling the helper, a cycle cannot call the same vertex repeatedly. The helper's base case handles src == dest immediately. To check only existence, use a visited array instead and omit predecessors. To reconstruct the found route, call recoverPath with the completed predecessor array.

The lecture DFS records $0\to1\to5\to3\to4\to7$, length 5. The graph also contains $0\to5\to7$, length 2. DFS is correctly answering “find a path”; it is not answering “find a shortest path”. This difference follows directly from pursuing one branch before checking nearby alternatives.

DFS is correct for reachability because every new call follows a real edge, so no unreachable vertex can be discovered. Conversely, if a reachable vertex remained undiscovered after the traversal, take a route from the source to it and locate the first undiscovered vertex. Its preceding vertex was discovered and eventually checked that edge, which would have discovered it. That contradiction proves every reachable vertex is found.

Practice. Should ordinary DFS reset pred[w] to -1 after an unsuccessful branch?

Iterative DFS: The Lecture Variant#

The lecture's explicit-stack version pushes neighbours and marks a vertex when popped. If a popped vertex is already visited, it skips it. This can put several pending copies of a vertex on the stack, so it is not merely BFS with the word “queue” replaced.

push src
while stack is not empty:
    v = pop
    if visited[v]: continue
    visited[v] = true
    for each neighbour w of v where not visited[w]:
        pred[w] = v
        push w

If neighbours are pushed in ascending order, the largest is on top and explored first. Push in reverse order if you want smaller pending neighbours to be popped first. Matching every detail of recursive DFS requires explicit stack frames holding a vertex and its next neighbour, rather than assuming any stack implementation gives identical predecessor choices.

Consider the triangle $0-1-2-0$, scanning neighbours ascending. Initially push 0. Pop and mark 0, then push 1 and 2: stack bottom-to-top is [1,2]. Pop and mark 2. Its neighbour 1 is pending but not visited, so push another 1 and overwrite pred[1]=2. Now [1,1] is pending. Pop the top 1, mark it; later skip the older copy.

The next custom trace shows exactly that mark-on-pop behaviour. Table values explicitly give stack order, since graph markers alone cannot show two occurrences of the same vertex.

The matrix Graph from 12. Graphs and Representations gives a complete implementation of this exact trace. pred[w] is assigned when a neighbour is pushed, so a later push can replace it. order records only first visits, not skipped duplicate pops. The caller supplies arrays of length at least GraphNumVertices(g).

// Add to the matrix Graph implementation in Note 12.
// Returns the number of vertices reached from src.
int GraphDfsIterative(Graph g, Vertex src, int pred[], Vertex order[]) {
    checkVertex(g, src);
    assert(pred != NULL && order != NULL);
    bool *visited = checkedCalloc((size_t)g->nV, sizeof *visited);
    // A first visit scans each adjacency once. Each of the 2E
    // directed adjacency entries can cause at most one push.
    size_t capacity = 2u * (size_t)g->nE + 1u;
    Vertex *stack = checkedCalloc(capacity, sizeof *stack);
    size_t top = 0;
    int count = 0;
    for (int v = 0; v < g->nV; v++) pred[v] = -1;
    stack[top++] = src;
    while (top > 0) {
        Vertex v = stack[--top];
        if (visited[v]) continue;
        visited[v] = true;
        order[count++] = v;
        for (Vertex w = 0; w < g->nV; w++) {
            if (g->edges[v][w] && !visited[w]) {
                pred[w] = v;
                assert(top < capacity);
                stack[top++] = w;
            }
        }
    }
    free(stack);
    free(visited);
    return count;
}

On the trace triangle, the returned order is 0,2,1 and the final predecessors are pred[0]=-1, pred[1]=2, pred[2]=0. The stack's size bound is 2E+1 slots even when several copies of a vertex are pending; it follows from counting oriented adjacency inspections, not from counting vertices. Because every reached vertex’s matrix row is scanned once, $R$ reached vertices take $\Theta(RV)$ scan work. Initialising arrays takes $\Theta(V)$ and the preallocated zeroed stack takes $O(E)$; total time is $O(V+E+RV)=O(V^2)$ and auxiliary space is $O(V+E)$. Replacing the matrix neighbour loop by list iteration gives $O(V+E)$ time while preserving the same duplicate-push bound. For a complete traversal of a disconnected graph, call this from each unvisited source or use an outer traversal loop as described below.

One vertex can have several pending copies, but its neighbours are scanned only on its first visit. Each inspected edge can cause at most one push in that orientation. Total pushes and pops are therefore $O(V+E)$ over a full traversal, with potentially $O(E)$ stack entries in a dense graph. Allocating just $V$ slots for this particular algorithm is not justified. Recursive DFS has at most $V$ simultaneous calls instead.

Practice. Why would marking on push change this triangle's result?

Costs and Complete Traversals#

For adjacency lists and constant-time queue/stack operations, each vertex is discovered or visited at most once, and its neighbour list is scanned once. The total list work is $\sum_v\deg(v)=2E$ for an undirected graph and $E$ for a directed graph. Thus a full traversal takes $\Theta(V+E)$ time, including initialising the vertex arrays.

With an adjacency matrix, the loop scans $V$ cells for each reached vertex. If $R$ vertices are reached, the traversal above costs $\Theta(V+RV)$ including initialisation; its worst case is $\Theta(V^2)$. It does not become $O(V+E)$ merely because the input is sparse. A naive edge-array implementation that rescans all edges per vertex can cost $O(VE)$.

Auxiliary space excludes the already stored graph. BFS uses $O(V)$ queue/arrays. Recursive DFS uses $O(V)$ arrays and up to $O(V)$ call-stack space, reached on a long chain. Mark-on-pop iterative DFS can additionally need $O(E)$ pending entries. Early termination can reduce actual work but does not change these worst-case bounds.

A traversal from one vertex reaches only its component in an undirected graph, or its outgoing-reachable region in a digraph. To cover all vertices, keep one shared visited array and restart from each still-unvisited vertex.

The discovery edges, one predecessor edge for each non-root reached vertex, form a tree for that component. The algorithm also inspects other edges; taking all inspected edges would retain cycles. Repeating over disconnected components gives a spanning forest with $V-C$ discovery edges.

Practice. If we run DFS from every unvisited vertex, why is the adjacency-list cost still $O(V+E)$ rather than $O(V(V+E))$?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. In an unweighted graph, BFS first discovers vertex v from u at distance 3. What is dist[v], and why may a later edge not improve it?

Question 2. Recursive DFS enters A, then B, then D; D has no unvisited neighbours. What call returns next, and what does a backtracking path search need to undo?

Question 3. A graph has two disconnected components. Why does one call to BFS from vertex 0 not constitute a full traversal, and what extra loop is required?