Graphs and traversal

Learning outcomes

Choose a graph representation, trace BFS and DFS, and distinguish shortest paths from minimum spanning trees.

12.1 Vertices, edges and representations

A graph G = (V, E) consists of vertices and edges. Directed edges have an orientation; undirected edges connect unordered pairs. A weighted graph associates costs with edges. A path follows edges, a cycle returns to its starting vertex, and connected components identify mutually reachable groups in an undirected graph.

For an undirected adjacency list, each edge is usually recorded twice. A matrix for an undirected graph is symmetric. A weighted representation must distinguish a missing edge from a zero-weight edge; using zero for both loses information. A graph's vertex set also includes isolated vertices, which do not appear in any edge pair.

12.2 Breadth-first search

BFS explores vertices in distance layers from a start vertex. Mark the start discovered and enqueue it. Repeatedly dequeue a vertex, examine its neighbours, and mark and enqueue each undiscovered neighbour. Mark when enqueuing, not later, to prevent repeated queue entries.

Use edges {0–1, 0–2, 1–3, 2–3, 2–4} and inspect neighbours in increasing numeric order.

Visit order is 0, 1, 2, 3, 4. BFS distances from 0 are 0, 1, 1, 2, 2. Store a predecessor when discovering each vertex to reconstruct a shortest path in an unweighted graph.

12.3 Depth-first search

DFS visits a vertex, marks it and recursively visits each undiscovered neighbour, completing one branch before returning. For the same graph and neighbour order, the lab produces 0, 1, 3, 2, 4. An explicit stack can replace recursion, though push order affects the resulting traversal order.

With adjacency lists, both BFS and DFS take Θ(V + E) for a full traversal. The lab also includes a self-loop at 2 and isolated vertex 5 as boundary tests; neither changes the stated traversal orders from 0. The supplied matrix lab scans a full row for each visited vertex, so its worst-case time is Θ(V²). Both need O(V) traversal state. To cover a disconnected graph, start another traversal at each still-undiscovered vertex; one starting vertex covers only its reachable component.

12.4 Dijkstra's shortest paths

Dijkstra's algorithm computes shortest-path distances from one source when edge weights are nonnegative. Initialise the source to zero and other distances to infinity. Repeatedly settle the unsettled vertex with smallest tentative distance, then relax its outgoing edges: replace a neighbour's distance if the path through the settled vertex is shorter. Stop if no reachable unsettled vertex remains.

For undirected edges A–B:4, A–C:1, C–B:2, B–D:1, C–D:5, D–E:3, B–E:7, the final distances from A are:

An array-based minimum selection gives O(V²) time. Adjacency lists with a suitable binary heap give O((V + E) log V). Negative edges invalidate the settling argument; use an algorithm whose assumptions permit them. Unreachable vertices remain at infinity, and code must avoid overflowing a distance when adding weights.

12.5 Minimum spanning trees

A spanning tree connects all vertices of a connected undirected graph without a cycle. It has V − 1 edges. An MST minimises total tree weight, not distance from one source.

Prim's algorithm grows one tree, repeatedly choosing a minimum-weight edge crossing from the selected vertices to an unselected vertex. Kruskal's algorithm processes edges in nondecreasing weight order and accepts an edge only when it joins different components, usually tracked by disjoint-set union.

For the complete graph on {1,2,3,4,5} with w(i,j) = |i − j|, the edges 1–2, 2–3, 3–4, 4–5 form a tree of total weight 4. Every spanning tree has four edges and every edge weighs at least 1, so no smaller total is possible. This supplies a lower-bound argument as well as a construction.

For a disconnected graph, the corresponding result is a minimum spanning forest. Equal weights may permit several MSTs. The choice between Prim and Kruskal depends on representation and implementation, not solely on the label “sparse” or “dense”.

Practice

1. Add isolated vertex 5 to the traversal example. Does BFS from 0 visit it?
2. Build the adjacency matrix for the five-vertex traversal graph.
3. Explain why BFS is not generally a weighted shortest-path algorithm.
4. Give a reason that a shortest-path tree and an MST can differ.
5. State what Kruskal's component test prevents.

/* C11. undirected graph with at most six vertices. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#define MAX_V 6

typedef struct { bool edge[MAX_V][MAX_V]; size_t n; } Graph;
static bool add_edge(Graph *g, size_t u, size_t v)
{
    if (g->n > MAX_V || u >= g->n || v >= g->n) return false;
    g->edge[u][v] = true; g->edge[v][u] = true;
    return true;
}
/* Return the count reached, or zero for an invalid start. out has MAX_V slots. */
static size_t bfs(const Graph *g, size_t start, size_t out[])
{
    if (g->n > MAX_V || start >= g->n) return 0;
    bool visited[MAX_V] = {false};
    size_t queue[MAX_V], front = 0, rear = 0, count = 0;
    queue[rear++] = start; visited[start] = true;
    while (front < rear) {
        size_t u = queue[front++]; out[count++] = u;
        for (size_t v = 0; v < g->n; ++v)
            if (g->edge[u][v] && !visited[v]) {
                visited[v] = true; /* Mark when enqueued: no duplicates. */
                queue[rear++] = v;
            }
    }
    return count;
}
static void visit(const Graph *g, size_t u, bool visited[], size_t out[], size_t *n)
{
    visited[u] = true; out[(*n)++] = u;
    for (size_t v = 0; v < g->n; ++v)
        if (g->edge[u][v] && !visited[v]) visit(g, v, visited, out, n);
}
static size_t dfs(const Graph *g, size_t start, size_t out[])
{
    if (g->n > MAX_V || start >= g->n) return 0;
    bool visited[MAX_V] = {false}; size_t n = 0;
    visit(g, start, visited, out, &n); return n;
}
static void show(const char *label, const size_t out[], const size_t expected[], size_t n)
{
    printf("%s:", label);
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %zu", out[i]); }
    putchar('\n');
}
int main(void)
{
    Graph g = {{{false}}, 6}; size_t out[MAX_V];
    assert(add_edge(&g, 0, 1)); assert(add_edge(&g, 0, 2));
    assert(add_edge(&g, 1, 3)); assert(add_edge(&g, 2, 3));
    assert(add_edge(&g, 2, 4)); assert(add_edge(&g, 2, 2)); /* self-loop */
    assert(!add_edge(&g, 0, 6));
    const size_t b[] = {0, 1, 2, 3, 4}, d[] = {0, 1, 3, 2, 4};
    size_t n = bfs(&g, 0, out); assert(n == 5); show("BFS", out, b, n);
    n = dfs(&g, 0, out); assert(n == 5); show("DFS", out, d, n);
    assert(bfs(&g, 5, out) == 1 && out[0] == 5); /* disconnected vertex */
    assert(dfs(&g, 5, out) == 1 && out[0] == 5);
    assert(bfs(&g, 6, out) == 0 && dfs(&g, 6, out) == 0);
    g.n = 0; assert(bfs(&g, 0, out) == 0 && dfs(&g, 0, out) == 0);
    puts("graph tests passed");
    return 0;
}