5.1 Graph representations, DFS, and BFS

A graph separates two questions that are easy to mix up: what relations exist, and how those relations are stored. Depth-first search (DFS) and breadth-first search (BFS) operate on the same abstract graph, but their frontiers impose different exploration orders. A rigorous trace must therefore state the graph representation, the order in which neighbours are inspected, and exactly when a vertex becomes discovered.

Choosing the next vertex

Graphs model roads, communication links, prerequisites, and program states. Unlike an array, a graph does not come with one natural “next” element. From a vertex there may be no outgoing edge, one outgoing edge, or many. A traversal needs a disciplined frontier and a record of what has already been discovered.

The stack and queue contracts give the frontier two different orders:

• DFS follows one unfinished route deeply and is naturally expressed by recursion or a stack.
• BFS processes the oldest discovered vertex first and therefore expands in distance layers through a queue.

Neither algorithm requires edge weights merely to visit vertices. When every edge has equal cost, however, BFS provides more: it computes the minimum number of edges from the source to every reachable vertex.

Graphs, paths, and reachability

Here a path is a vertex sequence whose consecutive vertices are joined by an edge; this broad usage is also called a walk, and vertices or edges may repeat. A simple path has no repeated vertex. Its unweighted length counts traversed edges, not vertices.

A closed walk starts and ends at the same vertex. A trail repeats no edge, and a closed trail is a closed walk with no repeated edge. Here cycle means simple cycle: a closed trail with at least one edge and no repeated vertex except its first and last. A graph with no cycle is acyclic.

Unless stated otherwise, the undirected examples use simple graphs, with no loops or parallel edges. Their cycles have at least three edges. Traversing A -> B -> A along one undirected edge uses that same edge twice, so it is a closed walk but not a cycle. In a directed graph, a cycle follows the arc directions: distinct arcs A -> B and B -> A can form a two-edge cycle. A self-loop is a one-edge cycle only in a model that permits loops. In an undirected multigraph, two distinct parallel edges can form a two-edge cycle, but distinguishing them requires edge identities. The traversal sketches below record vertices; they are not edge-identity-aware multigraph cycle tests.

Why a closed trail contains a cycle. Among the positive-length closed segments of a nonempty closed trail, choose one with the fewest edges. Any repetition of a vertex other than its identified endpoints would delimit a shorter positive-length closed segment. Thus the selected segment has no such repetition and is a cycle. Conversely every cycle is a nonempty closed trail. Therefore absence of cycles is equivalent to absence of nonempty closed trails; it is not equivalent to absence of closed walks.

Vertex v is reachable from u if a directed path from u to v exists. Reachability need not be symmetric in a directed graph. In an undirected graph, two vertices are connected when a path joins them, and the graph is connected when every pair is connected. A maximal connected part is a connected component. For a directed vertex, out-degree counts leaving edges and in-degree counts entering edges.

Choosing a representation

Let the vertices be indexed 0,1,...,|V|-1.

The representation changes the cost of obtaining neighbours:

An adjacency matrix can be appropriate for a dense graph or repeated direct edge queries. An adjacency list avoids scanning absent edges and is therefore the natural representation for the linear-time traversals analysed below. In an undirected adjacency list, each edge appears in two lists; this changes a factor of two, not the asymptotic bound.

Depth-first search

DFS discovers a vertex, chooses its first undiscovered neighbour, and suspends the current vertex while it explores that neighbour. Recursive calls remember the suspended work. When a vertex has no undiscovered neighbour left, the call finishes and control backtracks.

DFS-VISIT(u):
    discovered[u] = true
    process u
    for each v in Adj[u], in the stated order:
        if not discovered[v]:
            parent[v] = u
            DFS-VISIT(v)

DFS-FOREST(G):
    set every vertex to undiscovered and every parent to null
    for each vertex u in the stated vertex order:
        if not discovered[u]:
            DFS-VISIT(u)

Calling DFS-VISIT(s) explores exactly the vertices reachable from s. DFS-FOREST adds the outer loop needed to cover a disconnected graph. Each root produced by that loop begins another DFS tree. An explicit stack can replace recursion, but it must preserve the same neighbour-order convention if the same trace is desired: pushing several neighbours onto a last-in-first-out stack can reverse their processing order.

The parent edges form a DFS tree (or a forest under the outer loop). They record how each vertex was first discovered; non-tree edges remain part of the graph even though they are not parent edges.

Breadth-first search and its frontier invariant

BFS uses a first-in-first-out queue. The queue contains discovered vertices whose outgoing adjacency lists have not yet been completely processed. The safe discovery rule is crucial:

Mark a vertex discovered when it is enqueued, not later when it is dequeued.

BFS(G, s):
    for each vertex v:
        discovered[v] = false
        distance[v] = infinity
        parent[v] = null
    discovered[s] = true
    distance[s] = 0
    enqueue(Q, s)

    while Q is not empty:
        u = dequeue(Q)
        process u
        for each v in Adj[u], in the stated order:
            if not discovered[v]:
                discovered[v] = true
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(Q, v)

The assignment to discovered[v] occurs before enqueue(Q,v). Thus a second frontier vertex that also has an edge to v sees that v is already claimed and cannot enqueue it again. “Discovered” and “fully processed” are different states: a queued vertex is discovered even though it has not yet been dequeued.

As with DFS, one call explores only vertices reachable from the source. To traverse every component of an undirected graph, run BFS again from an undiscovered vertex until none remain.

Shortest paths and traversal cost

This statement is about equal-cost edges. If edges have unequal weights, a path with fewer edges can have greater total weight. Ordinary BFS then still minimizes edge count, but it does not necessarily minimize weighted cost.

For one source, let V_R be the reached vertices and E_R their outgoing edges. The traversal itself takes O(|V_R|+|E_R|). The displayed BFS also initializes arrays for every vertex, so its total time is O(|V|+|E_R|). A bound using only the reached part must account for initialization separately.

Why layers and edge counts give the bounds

For the BFS shortest-path property, use a layer invariant. Initially only s has distance 0. Whenever BFS discovers v while processing u, it assigns distance[v] = distance[u] + 1. Because the queue is first-in-first-out, every vertex at distance k is processed before any newly discovered vertex at distance k+1. Therefore a hypothetical shorter path to v would have had to reach v from an earlier layer and would have discovered it sooner. The first assigned distance is consequently minimal. Each parent pointer decreases the distance by exactly one, so the reconstructed chain has that minimal length.

For the running time, initialization and the outer loop cost O(|V|). A vertex becomes discovered once, so it enters the DFS recursion/stack or BFS queue once. Scanning all adjacency lists examines each directed edge once; an undirected edge is examined twice. Hence the total is O(|V|+|E|). With a matrix, processing each reached vertex scans a full row of |V| entries, so a whole-graph traversal is instead Theta(|V|^2).

Two traversals of the same graph

Consider the directed graph on vertices A,B,C,D,E,F, with the following adjacency-list order:

A: B, D
B: C, D
C: F, D, E
D: E
E: —
F: —

    A B C D E F
A   0 1 0 1 0 0
B   0 0 1 1 0 0
C   0 0 0 1 1 1
D   0 0 0 0 1 0
E   0 0 0 0 0 0
F   0 0 0 0 0 0

Common mistakes

• A source search does not automatically visit unreachable vertices; an outer loop is required for a full graph traversal.
• A directed matrix need not be symmetric, and directed reachability need not work in both directions.
• BFS guarantees minimum edge count, not minimum arbitrary weighted cost.
• Quoting O(|V|+|E|) while actually scanning every row of an adjacency matrix mixes two different representations.
• A DFS parent tree or BFS parent tree contains discovery edges, not every edge of the original graph.

Summary

• A graph may be directed or undirected and weighted or unweighted.
• Paths, cycles, reachability, and connectivity describe the abstract graph, independently of its storage representation.
• A matrix supports constant-time edge tests and uses quadratic space. One row scan is linear in |V|; scanning every row is quadratic. A list stores and scans existing neighbours.
• DFS uses recursion or a stack to go deep before backtracking.
• BFS uses a queue to expand reachable vertices in nondecreasing edge-distance layers.
• Robust BFS marks a vertex at enqueue time, guaranteeing at most one queue entry per vertex.
• BFS parent and distance arrays describe shortest paths in an unweighted graph.
• Adjacency-list DFS and BFS take O(|V|+|E|) for the whole graph.

Exercises

1. For the A–F graph, write the outgoing neighbours of C and the row of the adjacency matrix belonging to C. Explain why the list cost depends on out-degree while the matrix row scan does not.
2. Run recursive DFS from D. Then run BFS from D. Give the discovery order for each search using the fixed list order, and state which vertices are not reachable.
3. In the original BFS from A, explain why E receives distance 2 even though C also has an edge to E. Reconstruct the stored parent path.
4. Give the earliest queue state that contains a duplicate when visited marks are delayed until dequeue. Identify the two edges responsible.
5. A graph has 10,000 vertices and 20,000 directed edges. Compare the number of adjacency positions conceptually scanned by a whole-graph matrix traversal with the list-based asymptotic work.

Solutions