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.

Motivation

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 choice of frontier answers different questions:

• 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.

Definitions

A path, in the course terminology, is a vertex sequence in which every consecutive pair is joined by an edge; it may repeat vertices. A simple path does not repeat vertices. A path's unweighted length is its number of edges, not its number of vertices. A cycle begins and ends at the same vertex; a simple cycle repeats no other vertex. A graph with no cycle is acyclic.

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.

Theorem/proposition

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 a search from one source, the sharper bound uses only the reached vertices and scanned outgoing edges. The conventional whole-graph bound is stated because the outer-loop versions visit every component.

Proof sketch or proof idea

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).

Worked examples

Use the course graph on vertices A,B,C,D,E,F. It is directed, and we fix 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 but costs quadratic space and row scans; 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