Graphs, BFS, DFS, Union-Find¶

Graphs in C mean three things: (1) a data structure for the graph itself, (2) a way to traverse it, (3) a set of algorithms that build on the traversal. All three are easier once you have libprep::vec and libprep::queue — which is why this topic comes after them in 04_hashmaps_in_c.md and 05_trees_and_heaps.md. If you don’t have those yet, build them before you start graph problems.

Representing a Graph¶

Three representations, in order of what you should reach for:

Adjacency List (default)¶

An array of Vec<int> — one vector of neighbor indices per vertex.

typedef struct {
    Vec *adj;      // adj[u] is a Vec of neighbor indices
    size_t n;      // number of vertices
} Graph;

void graph_init(Graph *g, size_t n) {
    g->n = n;
    g->adj = malloc(n * sizeof(Vec));
    for (size_t i = 0; i < n; i++) vec_init(&g->adj[i]);
}

void graph_add_edge(Graph *g, int u, int v) {
    vec_push(&g->adj[u], v);
    vec_push(&g->adj[v], u);   // undirected; omit for directed
}

Memory: O(V + E). Iteration over neighbors of u is O(deg(u)). This is what 90% of study problems want.

Adjacency Matrix¶

A V x V array of bool (or int for weighted).

bool adj[V][V];   // adj[u][v] == true iff edge u->v exists

Memory: O(V²). Only reasonable for V ≤ ~1000. Fast for edge-existence queries (“is there an edge u-v?” — O(1) vs O(deg) for a list).

Use this when V is small and edges are dense. study problems where V is small (Course Schedule, Flood Fill on a grid) can benefit.

Edge List¶

Just an array of {u, v, w} structs. Compact. Useless for traversal, essential for Kruskal’s MST and Bellman-Ford.

typedef struct { int u, v, w; } Edge;
Edge edges[E];

Implicit Graphs¶

Many LC problems don’t build a graph struct at all — the graph is implicit in the input (a 2D grid where neighbors are the 4 or 8 adjacent cells, or a list of strings where neighbors are one-letter-different words). Recognize these; don’t build an adjacency list you don’t need.

BFS: The Template¶

void bfs(Graph *g, int src) {
    bool *visited = calloc(g->n, sizeof(bool));
    Queue q;
    queue_init(&q);
    queue_push(&q, src);
    visited[src] = true;

    while (!queue_empty(&q)) {
        int u = queue_pop(&q);
        /* visit u */
        for (size_t i = 0; i < g->adj[u].len; i++) {
            int v = (int)vec_get(&g->adj[u], i);
            if (!visited[v]) {
                visited[v] = true;
                queue_push(&q, v);
            }
        }
    }
    free(visited);
    queue_destroy(&q);
}

Uses: shortest path in unweighted graph, level-order traversal, connected components, word-ladder, rotting oranges (multi-source BFS — push all initial sources into the queue first).

Multi-source BFS: push all sources into the queue at the start with distance 0. Same code. Solves “minimum distance from any source” problems in O(V+E) instead of one BFS per source.

DFS: Recursive vs Iterative¶

Recursive (Clean)¶

void dfs_rec(Graph *g, int u, bool *visited) {
    if (visited[u]) return;
    visited[u] = true;
    /* visit u */
    for (size_t i = 0; i < g->adj[u].len; i++) {
        int v = (int)vec_get(&g->adj[u], i);
        dfs_rec(g, v, visited);
    }
}

Iterative (Safe for Deep Graphs)¶

void dfs_iter(Graph *g, int src) {
    bool *visited = calloc(g->n, sizeof(bool));
    Stack s;
    stack_init(&s);
    stack_push(&s, src);

    while (!stack_empty(&s)) {
        int u = stack_pop(&s);
        if (visited[u]) continue;
        visited[u] = true;
        /* visit u */
        for (size_t i = 0; i < g->adj[u].len; i++) {
            int v = (int)vec_get(&g->adj[u], i);
            if (!visited[v]) stack_push(&s, v);
        }
    }
    free(visited);
    stack_destroy(&s);
}

When to Prefer Iterative¶

With V = 10⁵ and a chain graph, recursive DFS blows the stack. Iterative doesn’t. Rule: if the input constraint on V is more than ~10⁴, prefer iterative. Below that, recursive is fine and shorter.

Note: iterative DFS visits nodes in reverse order compared to recursive (because the stack is LIFO). If the problem cares about order (e.g., “lexicographically smallest DFS path”), push neighbors in reverse to match.

Topological Sort¶

On a DAG (directed acyclic graph). Two approaches:

Kahn’s Algorithm (BFS-based)¶

void topo_sort(Graph *g, int *order) {
    int *indeg = calloc(g->n, sizeof(int));
    for (size_t u = 0; u < g->n; u++)
        for (size_t i = 0; i < g->adj[u].len; i++)
            indeg[(int)vec_get(&g->adj[u], i)]++;

    Queue q; queue_init(&q);
    for (size_t u = 0; u < g->n; u++) if (indeg[u] == 0) queue_push(&q, (int)u);

    int idx = 0;
    while (!queue_empty(&q)) {
        int u = queue_pop(&q);
        order[idx++] = u;
        for (size_t i = 0; i < g->adj[u].len; i++) {
            int v = (int)vec_get(&g->adj[u], i);
            if (--indeg[v] == 0) queue_push(&q, v);
        }
    }
    // if idx < g->n, cycle exists
}

Uses: Course Schedule I & II, Alien Dictionary, task scheduling.

DFS-based (Reverse Postorder)¶

DFS from each unvisited node, push to output on finish. Reverse the output. Equivalent result; sometimes cleaner code, but Kahn’s also detects cycles naturally.

Union-Find (Disjoint Set Union)¶

The unsung hero of graph problems. O(α(n)) per operation, effectively constant.

typedef struct { int *parent, *rank; size_t n; } DSU;

void dsu_init(DSU *d, size_t n) {
    d->n = n;
    d->parent = malloc(n * sizeof(int));
    d->rank   = calloc(n, sizeof(int));
    for (size_t i = 0; i < n; i++) d->parent[i] = (int)i;
}

int dsu_find(DSU *d, int x) {
    while (d->parent[x] != x) {
        d->parent[x] = d->parent[d->parent[x]];   // path compression by halving
        x = d->parent[x];
    }
    return x;
}

bool dsu_union(DSU *d, int a, int b) {
    int ra = dsu_find(d, a), rb = dsu_find(d, b);
    if (ra == rb) return false;
    if      (d->rank[ra] < d->rank[rb]) d->parent[ra] = rb;
    else if (d->rank[ra] > d->rank[rb]) d->parent[rb] = ra;
    else { d->parent[rb] = ra; d->rank[ra]++; }
    return true;
}

Uses: Number of Connected Components in Undirected Graph, Redundant Connection, Accounts Merge, Graph Valid Tree, Kruskal’s MST.

Two optimizations are what get you the inverse-Ackermann bound:

Path compression — collapse the tree during find. The halving variant above is simpler than full compression and empirically as fast.
Union by rank (or size) — attach the smaller tree under the larger.

Do both. One without the other degrades to O(log n) per op.

Dijkstra (Weighted Shortest Path)¶

Shortest path in a graph with non-negative edge weights. Uses your min-heap + adjacency list.

void dijkstra(Graph *g, int src, int *dist) {
    for (size_t i = 0; i < g->n; i++) dist[i] = INT_MAX;
    dist[src] = 0;

    MinHeap pq; heap_init(&pq);   // heap of (distance, vertex)
    heap_push(&pq, (Item){0, src});

    while (!heap_empty(&pq)) {
        Item t = heap_pop(&pq);
        int d = t.dist, u = t.v;
        if (d > dist[u]) continue;   // stale entry
        for (size_t i = 0; i < g->adj[u].len; i++) {
            Edge e = g->adj[u].data[i];
            int nd = d + e.w;
            if (nd < dist[e.v]) {
                dist[e.v] = nd;
                heap_push(&pq, (Item){nd, e.v});
            }
        }
    }
}

Complexity: O((V+E) log V) with a binary heap. The “stale entry” check is essential — with a min-heap that doesn’t support decrease-key, you leave old distances in the heap and skip them when popped.

Do not use Dijkstra on negative edges. For those, use Bellman-Ford (O(V*E), handles negatives, detects negative cycles).

What Most People Get Wrong About This¶

They use recursive DFS on 10⁵-node graphs and hit stack overflow, or they use adjacency matrix for a sparse graph and blow O(V²) memory. Pick your representation by the constraints: dense small graph → matrix, sparse → adjacency list, edge-based algorithm (Kruskal) → edge list. Same for recursion depth: constraint says V ≤ 10⁴, recursion is fine; V ≤ 10⁵, iterate.

Return to README.md · Next: 07_dp_bitwise_recursion.md