Graph Traversal

Graph representation answers “which vertices are adjacent?” Graph traversal turns that local operation into global knowledge: what is reachable, how far away it is, whether a cycle exists, which tasks can be ordered, and which directed vertices are mutually reachable. Two traversal disciplines—breadth first and depth first—support nearly all of these results.

The algorithms need only the following abstract graph interface. The Data Structures course develops adjacency-list and adjacency-matrix representations together with the queue and stack operations used by the traversals.

VERTEX_COUNT(G)          number of vertices, labeled 0 through V-1
NEIGHBORS(G, u)          iterable sequence of vertices v with edge u -> v

For an adjacency list, iterating every neighbor list over a complete traversal examines Theta(E) arcs. For an adjacency matrix, scanning every row costs Theta(V^2). Unless noted otherwise, Theta(V + E) bounds assume adjacency lists.

Traversal State

One Boolean visited[] is enough for basic reachability. Structural algorithms need to distinguish three states:

Useful companion arrays are:

• parent[v]: the edge that first discovered v;
• distance[v]: BFS edge distance from a source;
• discover[v], finish[v]: DFS timestamps;
• component[v]: a connected- or strongly-connected-component identifier.

The decisive invariant shared by BFS and DFS is:

A vertex changes from white exactly once. Therefore it is inserted into the frontier at most once and receives one traversal parent.

Mark a vertex when it is discovered, before adding it to the frontier. Marking only when removed allows several neighbors to enqueue or push the same white-looking vertex.

Breadth-First Search

Breadth-first search (BFS) explores vertices in nondecreasing number of edges from its source. A FIFO queue enforces the layer order.

BFS(G, s):
    for each vertex v:
        color[v] = WHITE
        distance[v] = infinity
        parent[v] = none
    color[s] = GRAY
    distance[s] = 0
    enqueue(s)

    while queue is not empty:
        u = dequeue()
        for each v in NEIGHBORS(G, u):
            if color[v] == WHITE:
                color[v] = GRAY
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(v)
        color[u] = BLACK

Queue Discipline

When a vertex at distance k is removed, every vertex ahead of it in the queue has distance k or k+1. Its undiscovered neighbors are assigned distance k+1 and appended behind all already discovered vertices. Thus the queue never lets a later layer overtake an earlier one.

BFS Trace

Use directed edges:

0 -> 1, 0 -> 2
1 -> 3, 1 -> 4
2 -> 4
3 -> 5
4 -> 5

Starting at 0 and reading neighbors numerically:

The parent chain for 5 is 5 <- 3 <- 1 <- 0, so one shortest path is 0,1,3,5. A different neighbor order might choose parent 4; the distance remains three.

Switch between breadth-first and depth-first frontier discipline on the same graph:

Distance Correctness

Claim. When BFS discovers v, distance[v] is the length of a shortest path from s to v in an unweighted graph.

Proceed by layer induction. The source has correct distance zero. Assume every vertex discovered at distance at most k has a shortest-path distance recorded. A vertex v first discovered from a distance-k vertex has a path of length k+1. If a shorter path existed, its predecessor on that path would have distance at most k-1; BFS would have processed that predecessor earlier and discovered v sooner. Contradiction. Therefore the recorded distance is shortest.

This theorem minimizes edge count, not arbitrary weights. Use Dijkstra, Bellman–Ford, or DAG relaxation when edge costs differ.

Path Recovery

The parent array stores a shortest-path tree rooted at the source. Walk backward from the destination, then reverse the collected vertices.

#include <stdbool.h>
#include <limits.h>
#include <stddef.h>

bool recover_path(size_t source, size_t target, const int parent[],
                  size_t vertex_count, size_t path[], size_t path_capacity,
                  size_t *path_length) {
    if (source >= vertex_count || target >= vertex_count ||
        parent == NULL || path == NULL || path_length == NULL ||
        vertex_count - 1U > (size_t) INT_MAX) {
        return false;
    }
    *path_length = 0U;

    size_t length = 0U;
    int current = (int) target;
    while (current >= 0 && length < vertex_count) {
        size_t vertex = (size_t) current;
        if (vertex >= vertex_count || length >= path_capacity) {
            return false;
        }
        path[length++] = vertex;
        if (vertex == source) {
            break;
        }
        current = parent[vertex];
    }
    if (length == 0 || path[length - 1] != source) {
        return false;                         /* target unreachable from source */
    }

    for (size_t left = 0, right = length - 1; left < right; ++left, --right) {
        size_t temporary = path[left];
        path[left] = path[right];
        path[right] = temporary;
    }
    *path_length = length;
    return true;
}

The output buffer may be smaller than vertex_count; path_capacity prevents overflow. Each parent value is validated before it becomes an array index, and the length guard detects cycles. Under the BFS invariant, parents move one layer closer to the source, so a valid chain cannot cycle. The int sentinel representation limits vertex labels to INT_MAX; a size_t parent array with a dedicated sentinel removes that restriction.

Depth-First Search

Depth-first search (DFS) explores one branch completely before returning to try a sibling. Recursion uses the call stack as its frontier.

DFS-VISIT(G, u):
    color[u] = GRAY
    discover[u] = ++time
    for each v in NEIGHBORS(G, u):
        if color[v] == WHITE:
            parent[v] = u
            DFS-VISIT(G, v)
    color[u] = BLACK
    finish[u] = ++time

DFS(G):
    initialize every vertex WHITE with no parent
    for each vertex u:
        if color[u] == WHITE:
            DFS-VISIT(G, u)

The outer loop matters: a call from one source reaches only its reachable region. A DFS forest covers disconnected undirected graphs and directed graphs with unreachable vertices.

Recursive DFS

The recursive invariant is:

While DFS-VISIT(u) is active, u is gray; every recursive descendant is reachable from u through tree edges; when it returns, all vertices reachable through currently white outgoing paths from u are black.

This postorder moment—after every descendant finishes—is the source of topological sorting, SCC algorithms, articulation points, and many tree-style computations on graphs.

Iterative DFS

Simply pushing all neighbors and marking them visited produces a valid DFS-like reachability traversal, but it does not reproduce recursive finish events. Structural algorithms need a frame containing both the vertex and the index of its next unexamined neighbor:

push frame (source, next_neighbor = 0)
mark source GRAY
while stack not empty:
    f = top frame
    if f has another neighbor v:
        advance f.next_neighbor
        if v is WHITE:
            mark v GRAY; set parent; push (v, 0)
    else:
        mark f.vertex BLACK; record finish time; pop

The frame emulates the suspended local state of one recursive call. Use this form when recursion depth may approach V and overflow the process stack.

Discovery Times

Assign a timestamp on entry and another on exit. For every vertex u, its DFS lifetime is the interval:

DFS intervals have the parenthesis property: for any two vertices, their intervals are disjoint, or one is completely nested inside the other. Partial overlap cannot occur because a recursive call must finish before its caller continues.

Vertex v is a descendant of u in the DFS forest exactly when:

This numerical test turns ancestry into constant-time comparisons after one traversal.

Edge Classification

For a directed graph, DFS classifies an examined arc (u,v):

• Tree edge: v is white and the edge discovers it.
• Back edge: v is gray; it points to an active ancestor.
• Forward edge: v is black and is a proper descendant of u, but this arc did not discover it.
• Cross edge: v is black and lies in another completed branch or tree.

Classification depends on traversal order, but the existence of a directed back edge does not: a directed graph is cyclic if and only if a DFS finds one.

In an undirected graph, each edge appears from both endpoints. The arc back to parent[u] is the reverse view of the tree edge, not evidence of a cycle. Ignore that one parent edge when testing cycles. Parallel edges require more care: a second edge to the parent can form a length-two multigraph cycle, so edge identity—not merely parent vertex—may need tracking.

Cycle Detection

Directed Cycles

Use the color rule directly:

typedef enum { WHITE, GRAY, BLACK } Color;

/* Graph-neighbor iteration is represented abstractly here. */
bool directed_cycle_visit(const Graph *g, int u, Color color[]) {
    color[u] = GRAY;
    for (size_t i = 0; i < graph_degree(g, u); ++i) {
        int v = graph_neighbor(g, u, i);
        if (color[v] == GRAY) {
            return true;
        }
        if (color[v] == WHITE && directed_cycle_visit(g, v, color)) {
            return true;
        }
    }
    color[u] = BLACK;
    return false;
}

A gray neighbor lies on the active recursion path, so the tree path from it to u plus (u,v) forms a cycle. Conversely, take the first DFS exploration to enter any directed cycle. Following cycle edges cannot finish all its vertices without encountering an edge to an active earlier cycle vertex; a back edge must appear.

Undirected Cycles

Pass the parent and reject an already-visited neighbor only when it is not the parent:

UNDIRECTED-CYCLE(u, parent):
    visited[u] = true
    for each neighbor v:
        if not visited[v] and UNDIRECTED-CYCLE(v, u): return true
        else if visited[v] and v != parent: return true
    return false

Self-loops are immediate cycles. Whether two parallel edges constitute a cycle depends on whether the course uses simple-graph or multigraph definitions; place that decision in the graph contract.

Bridges

In an undirected graph, a bridge is an edge whose removal increases the number of connected components. An articulation vertex is a vertex whose removal, together with its incident edges, increases that number. DFS finds both by measuring whether a child subtree has any route back above its parent.

Let discover[u] be u’s DFS time. Define low[u] as the smallest discovery time reachable from u’s DFS subtree by zero or more tree edges followed by at most one back edge. During return from child v:

low[u] = min(low[u], low[v])

if low[v] > discover[u]:
    tree edge (u,v) is a bridge

if u is not a DFS root and low[v] >= discover[u]:
    u is an articulation vertex

The strict bridge inequality means no vertex in v’s subtree has an edge to u or an ancestor of u; removing (u,v) disconnects that subtree. Equality is enough for articulation: a back edge reaching u still leaves the child subtree dependent on u after u itself is removed. A DFS root is an articulation vertex only when it has at least two DFS-tree children.

For a triangle 0-1-2-0 with a tail 1-3-4, the triangle’s low values return to discovery time of 0, so none of its three edges is a bridge. Vertex 4 has no back edge; low[4] > discover[3], making 3-4 a bridge. The same reasoning makes 1-3 a bridge and vertices 1 and 3 articulation points.

An implementation must identify the parent edge, not just the parent vertex. With parallel edges between u and v, one may be the DFS tree edge while the other is a valid back edge that prevents either copy from being a bridge. The traversal remains Theta(V+E) because every undirected edge is examined a constant number of times.

Connected Components

In an undirected graph, vertices u and v belong to the same connected component exactly when a traversal from one reaches the other.

component_count = 0
for each vertex s:
    if s is undiscovered:
        traverse from s, assigning component[v] = component_count
        component_count++

Each new root begins one component; traversal marks every vertex in it; no edge can join two different reported components, because that edge would have made one traversal reach the other endpoint. Total time is Theta(V+E) with adjacency lists.

For directed graphs, ordinary reachability is not symmetric. “Weakly connected” means connected after ignoring directions; “strongly connected” means mutually reachable and requires the SCC algorithms below.

Bipartite Testing

An undirected graph is bipartite when its vertices can be divided into two sets so every edge crosses between sets. BFS or DFS assigns alternating colors:

for each undiscovered root s:
    side[s] = 0
    traverse from s:
        for each edge u-v:
            if v is uncolored:
                side[v] = 1 - side[u]
                parent[v] = u
            else if side[v] == side[u]:
                report not bipartite

Every tree edge alternates side, so all colored edges satisfy the partition unless a same-side edge appears. Such an edge certifies an odd cycle: follow parent paths from its endpoints to their lowest common ancestor and add the conflict edge; equal endpoint parity makes the resulting cycle odd. Conversely, alternating two colors around an odd cycle would require its starting vertex to receive both colors, so no bipartition exists.

Disconnected graphs need a new colored root in every component. Self-loops fail immediately. If the interface must return a certificate, successful output is the two side arrays; failed output can reconstruct one odd cycle from the two parent chains rather than returning only a Boolean.

Topological Sorting

A topological order of a directed graph lists every vertex exactly once so that each edge u -> v places u before v. Such an order exists exactly for directed acyclic graphs (DAGs).

DFS Ordering

In a DAG, append a vertex when DFS finishes it, then reverse finish order. For every edge u -> v, either DFS visits v below u and finishes it first, or v was already black; a gray v would be a cycle. Thus finish[u] > finish[v], and reversing produces u before v.

A production DFS topological sort must detect gray edges and return failure. A visited[]-only version can emit an order for a cyclic graph without warning.

TOPO-VISIT(u):
    color[u] = GRAY
    for each v in neighbors(u):
        if color[v] == GRAY: return CYCLE
        if color[v] == WHITE and TOPO-VISIT(v) == CYCLE: return CYCLE
    color[u] = BLACK
    append u

Kahn Algorithm

Kahn’s algorithm repeatedly removes a vertex of indegree zero:

compute indegree[v] for every vertex
enqueue every vertex with indegree zero
while queue is not empty:
    u = dequeue()
    append u to order
    for each edge u -> v:
        indegree[v]--
        if indegree[v] == 0: enqueue(v)
if fewer than V vertices were appended: report a cycle

Invariant. indegree[v] counts incoming edges from vertices not yet output. A zero-indegree vertex has no remaining prerequisite and is safe to choose. If vertices remain but none has zero indegree, following an incoming edge repeatedly within the finite remaining graph must revisit a vertex, proving a directed cycle.

Both algorithms take Theta(V+E). DFS naturally supplies reverse postorder and integrates with other DFS analyses. Kahn’s algorithm exposes currently available tasks and makes cycle detection particularly visible. A priority queue can select the lexicographically smallest valid order, increasing cost to O((V+E) log V).

Strong Components

A strongly connected component (SCC) is a maximal set of directed vertices in which every vertex can reach every other. Contract each SCC into one supervertex; the resulting condensation graph is always a DAG. If it contained a cycle, all SCCs on that cycle would be mutually reachable and should have been one component.

Kosaraju Algorithm

Kosaraju uses two complete traversals:

1. Run DFS on G; push each vertex when it finishes.
2. Form transpose G^T by reversing every edge.
3. Clear visited state.
4. Pop vertices in decreasing finish time.
   For each unvisited popped vertex, DFS from it in G^T;
   that traversal is one SCC.

Why does the ordering work? In the condensation DAG, the SCC containing the latest-finishing first-pass vertex is a source under the relevant finish-time ordering. Transposing turns it into a sink: the second-pass traversal cannot escape into an unassigned SCC. It reaches exactly the mutually reachable vertices in its own SCC. Removing it exposes the same argument for the remaining condensation DAG.

Building the transpose and both traversals cost Theta(V+E) time and space.

Tarjan Algorithm

Tarjan finds SCCs in one DFS using:

• index[u]: discovery number;
• low[u]: smallest discovery index reachable from u through zero or more DFS-tree edges followed by at most one edge to a vertex still on the active stack;
• on_stack[u]: whether u belongs to an open candidate component.

After exploring u, if low[u] == index[u], then u is the root of an SCC. Pop through u; all popped vertices form that component.

STRONGCONNECT(u):
    index[u] = low[u] = next_index++
    push u; on_stack[u] = true

    for each u -> v:
        if v has no index:
            STRONGCONNECT(v)
            low[u] = min(low[u], low[v])
        else if on_stack[v]:
            low[u] = min(low[u], index[v])

    if low[u] == index[u]:
        repeat:
            v = pop; on_stack[v] = false; assign v to current SCC
        until v == u

The on_stack test is essential. An edge to a vertex in an already completed SCC must not lower low[u]; that component is closed and cannot be mutually reachable with u through the active DFS region.

SCC Trace

For edges 0->1, 1->2, 2->0, 2->3, 3->4, 4->3:

• DFS indices may be 0,1,2,3,4.
• Edge 2->0 lowers low[2] to 0; returns propagate low[1]=low[0]=0.
• Edge 4->3 lowers low[4] to 3; when 3 resumes, low[3]==index[3], so {4,3} is popped.
• Finally low[0]==index[0], so {2,1,0} is popped.

The cross-component edge 2->3 does not merge them because vertices 3 and 4 are popped before control returns to 2; there is no path back to the first component.

Tarjan runs in Theta(V+E) time and uses Theta(V) auxiliary state beyond the graph. It is compact but its low-link invariant is easier to implement incorrectly than Kosaraju’s two-pass method.

Traversal Costs

For whole-graph tasks, Theta(V+E) is optimal when any unseen vertex or edge could connect components, create a cycle, or change the answer. Single-source traversal need not inspect edges wholly inside unreachable components.

Traversal Failures

• Marking on dequeue/pop rather than discovery, causing duplicate frontier entries.
• Traversing only from vertex 0 when the task concerns the whole graph.
• Treating BFS as a weighted shortest-path algorithm.
• Reconstructing a path without checking that the destination was reached.
• Using the directed gray-edge rule unchanged on an undirected graph.
• Producing reverse DFS finish order without detecting a cycle.
• Mutating caller-owned indegrees in Kahn’s algorithm without documenting it.
• Updating Tarjan low[u] from low[v] for an already-discovered stack neighbor; that case uses index[v].
• Assuming traversal order is unique. Neighbor ordering can change parents, DFS trees, topological orders, and SCC numbering without changing validity.

Choosing a Traversal

• Need minimum number of edges from one source: BFS.
• Need reachability only: BFS or DFS; choose for surrounding needs and depth constraints.
• Need recursive structure, finish order, cycles, SCCs: DFS.
• Need an undirected bipartition or odd-cycle certificate: BFS or DFS with two colors.
• Need bridges or articulation vertices: DFS discovery and low-link values.
• Need a schedule plus a visible set of currently available tasks: Kahn.
• Need SCCs and prefer a simpler proof/implementation: Kosaraju.
• Need SCCs in one pass without storing a transpose: Tarjan.
• Need weighted optimal paths, spanning connections, or capacities: proceed to the specialized chapters; traversal is the substrate, not the final algorithm.

Traversal Review

• BFS uses a FIFO frontier and discovers vertices in shortest unweighted-distance layers.
• DFS uses recursive or explicit stack frames and exposes nested discovery/finish intervals.
• Parent arrays recover traversal paths; colors and timestamps expose graph structure.
• Directed cycles correspond to DFS back edges; undirected detection must ignore the parent edge.
• Repeated traversal roots identify undirected connected components.
• Undirected low links reveal bridges and articulation vertices; two-color traversal decides bipartiteness.
• DFS reverse finish order and Kahn’s indegree process both topologically sort a DAG and must reject cycles.
• Kosaraju uses finish order plus the transpose; Tarjan uses indices, low links, and an active stack.
• With adjacency lists, these algorithms have O(V+E) worst-case time; whole-graph traversals attain Theta(V+E), while one-source BFS is Theta(V+E_R) for arcs leaving reachable vertices.

Traversal Problems

Traversal Vocabulary

1. Explain the semantic difference between white, gray, and black.
2. Why must BFS mark a vertex before enqueueing it?
3. State the DFS parenthesis property.
4. Why is the SCC condensation graph acyclic?

Order Traces

5. Run BFS and recursive DFS on the worked graph using reverse numerical neighbor order. Record parents, BFS distances, DFS discovery times, and finish times.
6. Run Kahn’s algorithm on edges A->C, B->C, B->D, C->E, D->E. List the zero-indegree set after every removal.
7. Trace Tarjan on two directed cycles joined by a one-way edge. Record index, low link, and stack contents after every return.

Traversal Proofs

8. Prove that every BFS tree edge connects adjacent distance layers and every non-tree edge in an undirected graph connects vertices whose distances differ by at most one.
9. Prove that reversing DFS finish order is topological for a DAG.
10. Prove that if Kahn’s algorithm stops early, the remaining subgraph contains a directed cycle.
11. Prove the bridge test low[v] > discover[u] and explain why articulation uses >= for a nonroot parent.
12. Prove that a graph is bipartite exactly when it contains no odd cycle.

State Bugs

13. Construct a diamond graph where marking vertices only on dequeue enqueues one vertex twice.
14. Give an undirected tree that a naive gray-edge directed-cycle detector incorrectly reports as cyclic.
15. Give a cyclic directed graph for which a visited-only DFS “topological sort” still returns a list of all vertices.
16. Construct a two-parallel-edge graph where skipping every edge to the parent vertex falsely reports a bridge.

Traversal Implementations

17. Implement BFS against your Data Structures graph interface, including distance, parent, and safe path recovery.
18. Implement iterative DFS with explicit frames and verify its finish times match a recursive version under the same neighbor order.
19. Implement both SCC algorithms and compare the resulting partitions independent of component numbering.
20. Implement bridge, articulation, and bipartite certificate routines with explicit multigraph contracts.

Graph Models

21. Find the shortest transformation from one four-letter word to another when one letter may change at a time and every intermediate word must be in a dictionary. Define vertices, edges, and why BFS is correct.
22. Extend Kahn’s algorithm to return the lexicographically smallest topological order. Analyze the added data-structure cost.
23. Determine whether a directed graph has a unique topological order. Give conditions in terms of Kahn’s available set.

Graph Challenges

24. Derive an algorithm for finding a shortest directed cycle in an unweighted graph. State its complexity and explain why one BFS may not suffice.
25. Use SCC contraction to solve: “What is the minimum number of starting vertices needed to reach every vertex of a directed graph?” Prove the answer in terms of source components of the condensation DAG.
26. Orient every bridge-connected component into a compact bridge tree. Use that tree to answer how many edges must be added to make a connected undirected graph two-edge-connected.