Learn Zig Series (#118) - Graph Representation

scipio

Published: 25 Jul 2026 › Updated: 25 Jul 2026 Learn Zig Series (#118) - Graph Representation

Learn Zig Series (#118) - Graph Representation

What will I learn?

Why a graph is the right shape for data that is connected rather than ordered -- roads, dependencies, friendships, web links -- and why none of last week's line-of-elements tricks apply to it;
The three core representations -- edge list, adjacency matrix, and adjacency list -- and the exact space/time tradeoff that decides which one you reach for;
How to build a reusable, allocator-honest Graph type in Zig that handles directed and undirected edges without duplicating a single line of logic;
Extending that type to a weighted graph, because the moment you care about distances or costs an edge is more than a pair of node ids;
The CSR (compressed sparse row) layout -- how real graph libraries pack a static graph into two flat arrays for cache-friendly traversal;
A property-based test built on the handshake lemma (sum of degrees == 2 * edge count) that catches representation bugs no hand-picked example would;
How the same structures look in C, Rust and Go, and why "an array of lists" beats a fancy pointer-per-node graph in every language that cares about cache lines.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
Episode 117 (binary search) still warm -- we pay its three exercises in full compilable code at the top, so keep the half-open invariant and the rotated-array puzzle in mind;
Slices from episode 5, structs and tagged unions from episode 6, and above all the allocator discipline from episode 7 -- a graph is a dynamic, nested, heap-backed structure and every node's neighbour list has to be freed;
Comfort with std.ArrayList from episode 22, because an adjacency list is quite literally a list of lists;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#118) - Graph Representation

I ended last week promising that the web of connections was where we go next, and here we are. Everything in the last two episodes -- sorting a line of elements, then bisecting that line to find things fast -- rested on one quiet assumption: that the data lives on a line. Every element has a well-defined position relative to every other, "left half or right half" is always a meaningful question, and that is exactly what lets binary search throw away half the world in a single comparison. But a truly enormous amount of the most interesting data has no line through it at all. Cities are not "less than" each other -- they are connected by roads. Web pages are not sorted -- they link. People, package dependencies, network routers, neurons, molecules: all relationships, not rankings. To model that we need a structure built from nodes and the edges between them, and that structure is the graph. But first -- the search debt from episode 117, all three exercises, in real compilable code ;-)

Solutions to Episode 117 Exercises

Exercise 1 -- search a rotated sorted array. A sorted array rotated by some unknown amount (like [5, 8, 13, 1, 3, 4]) is no longer globally sorted, but here is the key observation: if you cut it at the middle, at least one of the two halves is still perfectly sorted. So at each step you work out which half is the sorted one, check whether the target falls inside its known range, and recurse into that half or the other. I switched back to inclusive [lo, hi] bounds here because the "is the target inside this sorted half?" test reads more naturally with a real last index than with a one-past-the-end hi:

const std = @import("std");

fn eq(comptime T: type, a: T, b: T, lessThan: fn (T, T) bool) bool {
    return !lessThan(a, b) and !lessThan(b, a);
}

fn searchRotated(comptime T: type, items: []const T, target: T, lessThan: fn (T, T) bool) ?usize {
    if (items.len == 0) return null;
    var lo: usize = 0;
    var hi: usize = items.len - 1; // inclusive bounds this time
    while (lo <= hi) {
        const mid = lo + (hi - lo) / 2;
        if (eq(T, items[mid], target, lessThan)) return mid;
        if (!lessThan(items[mid], items[lo])) {
            // left half [lo, mid] is the sorted one
            if (!lessThan(target, items[lo]) and lessThan(target, items[mid])) {
                if (mid == 0) return null;
                hi = mid - 1;
            } else lo = mid + 1;
        } else {
            // right half [mid, hi] is the sorted one
            if (lessThan(items[mid], target) and !lessThan(items[hi], target)) {
                lo = mid + 1;
            } else {
                if (mid == 0) return null;
                hi = mid - 1;
            }
        }
    }
    return null;
}

fn ltU32(a: u32, b: u32) bool {
    return a < b;
}

test "rotated search finds keys and reports absence" {
    const xs = [_]u32{ 5, 8, 13, 1, 3, 4 };
    try std.testing.expectEqual(@as(?usize, 2), searchRotated(u32, &xs, 13, ltU32));
    try std.testing.expectEqual(@as(?usize, 3), searchRotated(u32, &xs, 1, ltU32));
    try std.testing.expectEqual(@as(?usize, 0), searchRotated(u32, &xs, 5, ltU32));
    try std.testing.expectEqual(@as(?usize, null), searchRotated(u32, &xs, 99, ltU32));
    const sorted = [_]u32{ 1, 3, 4, 5, 8, 13 }; // rotation of 0
    try std.testing.expectEqual(@as(?usize, 4), searchRotated(u32, &sorted, 8, ltU32));
}

The two if (mid == 0) return null; guards are not decoration -- with unsigned usize indices, hi = mid - 1 when mid is 0 would wrap around to a gigantic number and then read wildly out of bounds. When mid is 0 the sorted half has nothing left of it anyway, so bailing out is correct and safe. A rotation of 0 is just the ordinary sorted case, and the same code handles it -- one half is trivially sorted, the target-in-range test does the rest.

Exercise 2 -- find a peak without a sorted array. Given a slice where no two adjacent elements are equal, a "peak" is any element strictly greater than both its neighbours (the two ends get an imaginary minus-infinity just past them). The magic is that even though the array as a whole is NOT sorted, the question "am I on an upward slope?" is monotone enough for bisection: if items[mid] < items[mid+1], there must be a peak somewhere to the right (worst case you keep climbing until the array ends, which is itself a peak). Otherwise a peak sits at mid or to its left. So we always walk toward higher ground:

fn findPeak(comptime T: type, items: []const T, lessThan: fn (T, T) bool) usize {
    var lo: usize = 0;
    var hi: usize = items.len - 1;
    while (lo < hi) {
        const mid = lo + (hi - lo) / 2;
        if (lessThan(items[mid], items[mid + 1])) {
            lo = mid + 1; // going uphill: a peak lies to the right
        } else {
            hi = mid; // items[mid] >= items[mid+1]: a peak is here or left
        }
    }
    return lo;
}

test "peak finding lands on a genuine peak in log n" {
    const xs = [_]u32{ 1, 4, 7, 6, 2, 9, 8 };
    const p = findPeak(u32, &xs, ltU32);
    const left_ok = p == 0 or xs[p] > xs[p - 1];
    const right_ok = p == xs.len - 1 or xs[p] > xs[p + 1];
    try std.testing.expect(left_ok and right_ok);
}

Note the test does not hard-code an index -- that array has two valid peaks (7 at index 2 and 9 at index 5), and any peak is a correct answer, so the test asserts the returned index actually IS a peak in stead of demanding a specific one. That is the honest way to test a function that is allowed to return any of several right answers.

Exercise 3 -- interpolation search. For uniformly distributed numeric keys, always halving is leaving money on the table -- if you are looking for a value near the top of the range, why probe the middle? Interpolation search guesses the probe position from the key's actual value, the way you would open a phone book near the back to find "Zwart". The estimate lo + (target - items[lo]) * (hi - lo) / (items[hi] - items[lo]) can overflow if you multiply two big u64s, so I widen to u128 for the one multiply and guard the zero-span case:

fn interpolationSearch(items: []const u64, target: u64) ?usize {
    if (items.len == 0) return null;
    var lo: usize = 0;
    var hi: usize = items.len - 1;
    while (lo <= hi and target >= items[lo] and target <= items[hi]) {
        if (items[hi] == items[lo]) {
            return if (items[lo] == target) lo else null;
        }
        const span = items[hi] - items[lo];
        // u128 multiply keeps the estimate overflow-proof
        const num = @as(u128, target - items[lo]) * @as(u128, hi - lo);
        const pos = lo + @as(usize, @intCast(num / span));
        if (items[pos] == target) return pos;
        if (items[pos] < target) lo = pos + 1 else {
            if (pos == 0) return null;
            hi = pos - 1;
        }
    }
    return null;
}

test "interpolation search on uniform keys" {
    const xs = [_]u64{ 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    try std.testing.expectEqual(@as(?usize, 5), interpolationSearch(&xs, 50));
    try std.testing.expectEqual(@as(?usize, 0), interpolationSearch(&xs, 0));
    try std.testing.expectEqual(@as(?usize, 9), interpolationSearch(&xs, 90));
    try std.testing.expectEqual(@as(?usize, null), interpolationSearch(&xs, 45));
}

On uniform data this is O(log log n) -- absurdly fast -- but on skewed data (say, keys that grow exponentially) the estimate is consistently wrong and it degrades all the way to O(n). That is exactly why plain binary search stays the boring default: it is O(log n) no matter WHAT the distribution looks like, and predictable-always beats fast-sometimes when you cannot control your input. Debt paid. Now, graphs ;-)

What a graph actually is

Strip away the pictures and a graph is two sets: a set of vertices (also called nodes) and a set of edges, where each edge joins a pair of vertices. That is the whole definition, and its bareness is the point -- almost everything relational fits it. The moment you add a little structure you get the vocabulary you will use for the rest of this arc:

An undirected edge is a two-way relationship (a road you can drive both ways, a friendship). A directed edge (an "arc") goes one way only (a one-way street, "A follows B on some feed", "task A must finish before task B").
A weighted edge carries a number -- distance, cost, capacity, latency. An unweighted edge just says "these two are connected".
The degree of a vertex is how many edges touch it. In a directed graph that splits into in-degree and out-degree.
Graphs can have cycles (a loop of edges leading back to the start) or be acyclic. A connected acyclic undirected graph is exactly a tree -- which means every tree we built in episodes 106 through 110 was secretly a graph all along, just a very well-behaved one.

We will label vertices with plain usize integers 0, 1, 2, ..., because integers make superb array indices, and the entire art of graph representation is really the art of storing "which vertices are adjacent to which" in a way that answers your questions quickly without wasting memory. There are three classic answers, and each one is a different bet about the shape of your graph. Let's build all three.

The edge list: the simplest thing that works

The most literal translation of the definition is to just store the list of edges. Nothing else. A graph is a []Edge, where each Edge is a pair of vertex ids:

const Edge = struct { from: usize, to: usize };

test "edge list: the whole graph is just a list of pairs" {
    const gpa = std.testing.allocator;
    var edges: std.ArrayList(Edge) = .empty;
    defer edges.deinit(gpa);
    try edges.append(gpa, .{ .from = 0, .to = 1 });
    try edges.append(gpa, .{ .from = 1, .to = 2 });
    try edges.append(gpa, .{ .from = 2, .to = 0 });

    var count: usize = 0; // "who touches node 1?" -> full scan, O(E)
    for (edges.items) |e| {
        if (e.from == 1 or e.to == 1) count += 1;
    }
    try std.testing.expectEqual(@as(usize, 2), count);
}

Notice the std.ArrayList init in modern Zig is .empty, and every mutating method takes the allocator explicitly (edges.append(gpa, ...), edges.deinit(gpa)) -- the list itself holds no allocator, which is the unmanaged style the standard library standardised on. The edge list is compact (O(E) space, nothing wasted) and it is the natural format to read a graph in from a file -- most graph datasets on disk are literally one "u v" pair per line. But look at that scan: answering "what is node 1 connected to?" means walking every single edge, O(E). For any algorithm that repeatedly asks "give me the neighbours of this vertex" -- which is nearly all of them -- an edge list is hopeless. It is a storage format, not a working representation. Having said that, keep it in your back pocket: some algorithms (Kruskal's minimum spanning tree, which sorts all edges by weight) want exactly this and nothing more.

The adjacency matrix: O(1) lookups, O(V-squared) memory

The opposite extreme optimises for one question -- "is there an edge between A and B?" -- and answers it in constant time. Allocate a V-by-V grid of booleans; cell [a][b] is true if an edge exists. Zig has no built-in 2D array over a runtime size, so the idiomatic move is a single flat slice indexed as a * n + b (the same row-major trick we used for images back in episode 44):

const Matrix = struct {
    n: usize,
    cells: []bool,
    gpa: std.mem.Allocator,

    fn init(gpa: std.mem.Allocator, n: usize) !Matrix {
        const cells = try gpa.alloc(bool, n * n);
        @memset(cells, false);
        return .{ .n = n, .cells = cells, .gpa = gpa };
    }
    fn deinit(self: *Matrix) void {
        self.gpa.free(self.cells);
    }
    fn addEdge(self: *Matrix, a: usize, b: usize) void {
        self.cells[a * self.n + b] = true;
        self.cells[b * self.n + a] = true; // undirected -> symmetric
    }
    fn connected(self: *const Matrix, a: usize, b: usize) bool {
        return self.cells[a * self.n + b];
    }
};

test "adjacency matrix: O(1) edge test, O(V^2) space" {
    const gpa = std.testing.allocator;
    var m = try Matrix.init(gpa, 4);
    defer m.deinit();
    m.addEdge(0, 1);
    m.addEdge(1, 2);
    try std.testing.expect(m.connected(0, 1));
    try std.testing.expect(m.connected(1, 0));
    try std.testing.expect(!m.connected(0, 3));
}

For an undirected graph the matrix is symmetric, so addEdge sets both cells. The lookup is a single array read -- unbeatable. The catch is right there in the allocation: n * n cells no matter how few edges you actually have. A social network with a million users would need a bool array of a trillion entries -- a terabyte -- to store what is in reality a very sparse set of friendships. So the matrix is the correct choice only for dense graphs (where the number of edges is a large fraction of the possible V*V/2), or for small V, or when you genuinely need that O(1) "are these two adjacent?" test in a hot loop. For the sparse graphs that dominate the real world, it is a catastrophe of wasted zeros. Which brings us to the representation you will actually use most days.

The adjacency list: the workhorse

The adjacency list stores, for each vertex, a list of just its neighbours. No cell for the edges that do not exist. It is O(V + E) space -- you pay for the vertices you have plus the edges you have, and nothing more -- and iterating a vertex's neighbours (the single most common operation in every traversal algorithm) is optimal, because they are sitting right there in a contiguous list. In Zig this is, quite literally, a list of lists. Here is a reusable Graph type that supports both directed and undirected edges from the same code:

const Graph = struct {
    gpa: std.mem.Allocator,
    adj: std.ArrayList(std.ArrayList(usize)),
    directed: bool,

    fn init(gpa: std.mem.Allocator, n: usize, directed: bool) !Graph {
        var adj: std.ArrayList(std.ArrayList(usize)) = .empty;
        try adj.ensureTotalCapacity(gpa, n);
        var i: usize = 0;
        while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
        return .{ .gpa = gpa, .adj = adj, .directed = directed };
    }
    fn deinit(self: *Graph) void {
        for (self.adj.items) |*list| list.deinit(self.gpa);
        self.adj.deinit(self.gpa);
    }
    fn addEdge(self: *Graph, from: usize, to: usize) !void {
        try self.adj.items[from].append(self.gpa, to);
        if (!self.directed) try self.adj.items[to].append(self.gpa, from);
    }
    fn neighbors(self: *const Graph, v: usize) []const usize {
        return self.adj.items[v].items;
    }
    fn degree(self: *const Graph, v: usize) usize {
        return self.adj.items[v].items.len;
    }
    fn hasEdge(self: *const Graph, from: usize, to: usize) bool {
        for (self.adj.items[from].items) |nb| {
            if (nb == to) return true;
        }
        return false;
    }
};

test "adjacency list graph: build and query" {
    const gpa = std.testing.allocator;
    var g = try Graph.init(gpa, 5, false);
    defer g.deinit();
    try g.addEdge(0, 1);
    try g.addEdge(0, 2);
    try g.addEdge(1, 2);
    try g.addEdge(3, 4);
    try std.testing.expectEqual(@as(usize, 2), g.degree(0));
    try std.testing.expect(g.hasEdge(0, 1));
    try std.testing.expect(g.hasEdge(1, 0));
    try std.testing.expect(!g.hasEdge(0, 4));
    try std.testing.expectEqual(@as(usize, 2), g.neighbors(0).len);
}

Several design decisions here are worth a stare. The directed flag is stored once and consulted in exactly one place -- addEdge -- so an undirected edge is just "add it in both directions" and everything else (traversal, degree, neighbour iteration) is written once and works for both kinds of graph. That is the mechanism-versus-policy split again: the storage does not know or care whether the graph is directed, it just stores lists. The deinit is the part that separates a Zig programmer from a tourist -- because each vertex owns a heap-allocated neighbour list, freeing the graph means freeing every inner list first and only then the outer list. Forget the loop and you leak V allocations. This is precisely the allocator honesty we drilled in episode 7, and running these tests on std.testing.allocator means a single forgotten deinit fails the test loudly in stead of silently bleeding memory. Note also ensureTotalCapacity followed by appendAssumeCapacity -- we know up front we want n empty lists, so we reserve once and then the appends cannot fail, a small tidy pattern for "I know exactly how many I need".

The one weakness: hasEdge is O(degree), because it scans the neighbour list. If your workload is dominated by "are these two specific vertices adjacent?" queries, that is the one thing the matrix does better. For the traversal algorithms that are coming, though, we never ask that -- we ask "give me all neighbours", and the adjacency list nails it.

Weighted graphs: an edge is more than a pair

The instant you care about distance or cost -- the shortest route, the cheapest network, the fastest pipeline -- an edge needs to carry a number. The change is tiny: in stead of a neighbour being a bare usize, it becomes a little struct pairing the destination with its weight. Everything else about the adjacency-list structure carries straight over:

const WeightedGraph = struct {
    const Neighbor = struct { to: usize, weight: i64 };
    gpa: std.mem.Allocator,
    adj: std.ArrayList(std.ArrayList(Neighbor)),

    fn init(gpa: std.mem.Allocator, n: usize) !WeightedGraph {
        var adj: std.ArrayList(std.ArrayList(Neighbor)) = .empty;
        try adj.ensureTotalCapacity(gpa, n);
        var i: usize = 0;
        while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
        return .{ .gpa = gpa, .adj = adj };
    }
    fn deinit(self: *WeightedGraph) void {
        for (self.adj.items) |*list| list.deinit(self.gpa);
        self.adj.deinit(self.gpa);
    }
    fn addEdge(self: *WeightedGraph, from: usize, to: usize, weight: i64) !void {
        try self.adj.items[from].append(self.gpa, .{ .to = to, .weight = weight });
        try self.adj.items[to].append(self.gpa, .{ .to = from, .weight = weight });
    }
};

test "weighted graph carries a cost on every edge" {
    const gpa = std.testing.allocator;
    var g = try WeightedGraph.init(gpa, 3);
    defer g.deinit();
    try g.addEdge(0, 1, 7);
    try g.addEdge(1, 2, 3);
    var total: i64 = 0;
    for (g.adj.items[1].items) |nb| total += nb.weight;
    try std.testing.expectEqual(@as(i64, 10), total);
}

That Neighbor struct is the seed of a lot of what is coming: the algorithms that find shortest paths spend their whole lives looking at nb.weight to decide which edge to relax next. I used i64 for the weight so negative edges are representable -- some graphs genuinely have them (a currency exchange where a cycle of trades nets you a profit is a negative-weight cycle) -- even though a couple of the classic algorithms will refuse to run when they show up. We are only building the container today; the reasoning that walks it comes in the next few episodes.

Performance: the CSR layout for static graphs

The adjacency list has one hidden cost that does not show up in the big-O: every vertex's neighbour list is a separate heap allocation, scattered across memory, so walking the whole graph means chasing pointers all over the place and missing the cache constantly (the same pointer-chasing tax we measured on linked lists back in episode 106). When the graph is static -- built once, then traversed many times, never modified -- you can do dramatically better with CSR, compressed sparse row. The idea: pack every neighbour into ONE flat array, and keep a second small array of offsets marking where each vertex's slice begins. Building it is a lovely little counting-sort-flavoured pass:

const Csr = struct {
    offsets: []usize, // length n+1
    targets: []usize, // length E
    gpa: std.mem.Allocator,

    fn build(gpa: std.mem.Allocator, n: usize, edges: []const Edge) !Csr {
        const offsets = try gpa.alloc(usize, n + 1);
        @memset(offsets, 0);
        for (edges) |e| offsets[e.from + 1] += 1; // out-degree per node
        var i: usize = 0;
        while (i < n) : (i += 1) offsets[i + 1] += offsets[i]; // prefix sum -> row starts
        const targets = try gpa.alloc(usize, edges.len);
        const cursor = try gpa.alloc(usize, n);
        defer gpa.free(cursor);
        @memcpy(cursor, offsets[0..n]);
        for (edges) |e| {
            targets[cursor[e.from]] = e.to;
            cursor[e.from] += 1;
        }
        return .{ .offsets = offsets, .targets = targets, .gpa = gpa };
    }
    fn deinit(self: *Csr) void {
        self.gpa.free(self.offsets);
        self.gpa.free(self.targets);
    }
    fn neighbors(self: *const Csr, v: usize) []const usize {
        return self.targets[self.offsets[v]..self.offsets[v + 1]];
    }
};

test "CSR packs a static graph into two flat arrays" {
    const gpa = std.testing.allocator;
    const edges = [_]Edge{
        .{ .from = 0, .to = 1 }, .{ .from = 0, .to = 2 },
        .{ .from = 1, .to = 2 }, .{ .from = 2, .to = 0 },
    };
    var csr = try Csr.build(gpa, 3, &edges);
    defer csr.deinit();
    try std.testing.expectEqualSlices(usize, &[_]usize{ 1, 2 }, csr.neighbors(0));
    try std.testing.expectEqualSlices(usize, &[_]usize{2}, csr.neighbors(1));
    try std.testing.expectEqualSlices(usize, &[_]usize{0}, csr.neighbors(2));
}

The build is three passes: count each vertex's out-degree into offsets (shifted by one slot on purpose), turn those counts into starting positions with a running prefix sum, then place each edge's target using a per-vertex cursor that advances as we fill. After that, neighbors(v) is a single slice targets[offsets[v]..offsets[v+1]] -- no allocation, no pointer chase, and the whole neighbour set of the graph is one contiguous block that the prefetcher loves. The tradeoff is baked into the name: CSR is static. You cannot cheaply add an edge to vertex 3 without shifting everything after it. So this is the "compile the graph once, then blast through it" representation -- exactly what a routing engine or a PageRank pass wants, and precisely wrong for a graph you are still building. Only two allocations survive (offsets and targets); cursor is scratch and freed on the way out.

Testing a graph the right way

Hand-picked graphs miss bugs the same way hand-picked arrays did last week, so we lean on the same discipline: property-based testing against an invariant that must hold for every graph. My favourite for undirected graphs is the handshake lemma -- in any undirected graph the sum of all vertex degrees equals exactly twice the number of edges (every edge contributes one to the degree of each of its two endpoints, so it is counted twice). If our addEdge/degree code ever disagrees with that, something is wrong with how edges are stored. So we throw hundreds of random graphs at it:

test "handshake lemma: degree sum is twice the edge count" {
    const gpa = std.testing.allocator;
    var prng = std.Random.DefaultPrng.init(0xBEEF);
    const rand = prng.random();
    var round: usize = 0;
    while (round < 200) : (round += 1) {
        const n = rand.intRangeAtMost(usize, 1, 30);
        var g = try Graph.init(gpa, n, false);
        defer g.deinit();
        const m = rand.intRangeAtMost(usize, 0, 40);
        var added: usize = 0;
        var e: usize = 0;
        while (e < m) : (e += 1) {
            const a = rand.uintLessThan(usize, n);
            const b = rand.uintLessThan(usize, n);
            if (a == b) continue; // skip self-loops for this invariant
            try g.addEdge(a, b);
            added += 1;
        }
        var degree_sum: usize = 0;
        var v: usize = 0;
        while (v < n) : (v += 1) degree_sum += g.degree(v);
        try std.testing.expectEqual(2 * added, degree_sum);
    }
}

Two hundred random graphs, sizes from 1 to 30 vertices, up to 40 random edges each, and every single one must satisfy degree_sum == 2 * added. The if (a == b) continue matters: a self-loop (an edge from a vertex to itself) breaks the "counted twice on two different vertices" reasoning -- some definitions say a self-loop adds two to a vertex's degree, others say one -- so I sidestep the ambiguity by not generating them, and I only count the edges I actually added. And because it all runs on std.testing.allocator, the deinit loop over the inner lists is silently under test too: leak one neighbour list and the harness fails the round. One property, hundreds of graphs, far more coverage than any drawing I could put on a whiteboard.

How C, Rust, and Go do it

In C, there is no standard graph type -- you roll your own, and the honest idiomatic version is exactly our adjacency list: an array of struct Node* head pointers, each a hand-linked list of neighbours, all of it manually malloc'd and free'd. It works, but you own every allocation and every dangling-pointer risk, and freeing the graph is the same nested loop we wrote -- except a forgotten free in C is a silent leak with no testing.allocator to catch you. Many C graph codebases skip the linked list entirely and go straight to a CSR pair of int arrays, because in C the manual bookkeeping is the same either way and CSR is faster.

In Rust, the ownership model makes a pointer-per-node graph genuinely painful (a node owned by its neighbours who are owned by it is a borrow-checker knot), so the community converged on exactly the shape we built: vertices are usize indices, and the graph is a Vec<Vec<usize>> or the excellent petgraph crate, which stores edges in flat vectors indexed by integer handles. It is not a coincidence that idiomatic Rust graphs look like our Zig ones -- "index into a flat array" sidesteps the ownership tangle that pointers create, in both languages.

In Go, you would write map[int][]int (a map from vertex to its slice of neighbours) or, if the vertices are dense integers, a plain [][]int -- which is our adjacency list with the garbage collector handling the frees. The map version buys you sparse, arbitrary vertex labels for the price of hashing on every lookup; the slice version is faster but wants contiguous integer ids. Go's GC means you never write the deinit loop, which is convenient right up until you are chasing why a long-running service's memory keeps climbing.

Our Zig versions sit where Zig always sits: the vertex-as-index design gives us the cache-friendly, borrow-checker-free layout Rust arrives at by necessity, but we keep explicit control of every allocation the way C does -- and the testing.allocator catches the leaks that C would let slide. Same handful of ideas in four languages, and in every one of them "an array of lists of integers" quietly wins over "a web of pointers". Bam, jonguh ;-)

Exercises

Directed in-degree and out-degree. Extend the Graph type with two methods for the directed case: outDegree(v) (trivial -- it is the length of v's neighbour list) and inDegree(v) (harder -- you must scan every vertex's list counting how many point at v, which is O(V + E)). Then write a hasCycleHint helper that returns true if any vertex has in-degree zero -- a necessary (not sufficient) property of a graph that could be a valid dependency order. Test it on a small directed acyclic graph and on one with a cycle.
Load a graph from text. Write fromEdgeText(gpa, n, text) that parses a multi-line string where each line is two space-separated integers "u v" (use std.mem.tokenizeScalar from episode 5) and builds an undirected Graph. Feed it a small map, then verify with the handshake lemma that the degree sum matches twice the line count. This is how nearly every real graph dataset arrives -- as an edge list on disk.
Convert adjacency list to CSR and prove they agree. Write toCsr(self, gpa) on Graph that flattens the adjacency list into the Csr layout from this episode. Then write a test that, for a random graph, checks that csr.neighbors(v) contains exactly the same vertex set as graph.neighbors(v) for every v (sort both slices first, since CSR build order may differ). You will have converted the "easy to build" representation into the "fast to traverse" one -- the exact pipeline a real graph engine runs at load time.

Where this is heading

We now have the graph sitting in memory in three shapes, and we can ask it who-is-next-to-whom in optimal time. But we have not yet gone anywhere in it. Building the container is the easy half; the interesting half is the walking. Given a starting vertex, how do you visit every other vertex reachable from it -- exactly once, no vertex missed, none visited twice, no matter how many cycles the graph loops back through? And it turns out there are two fundamentally different disciplines for that walk -- one that fans out in rings of ever-increasing distance, and one that plunges as deep as it can before backing up -- and the only difference between them is whether you pull the next vertex to visit from the front or the back of the pending pile. Two data structures we already know, one tiny swap, two completely different ways of seeing a graph. That is where we go next ;-)

Bedankt voor het lezen, en tot de volgende keer!

@scipio

Leave Learn Zig Series (#118) - Graph Representation to:

Written by scipio

Does it matter who's right, or who's left?

Best Posts From scipio

We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

Learn Zig Series (#118) - Graph Representation