Graph type we built in episode 118, and why it hands you shortest paths in an unweighted graph for free;Graph adjacency-list type, and we pay its three exercises in full compilable code at the top;visited array and a queue or a stack, and every one of those is a heap allocation that has to be freed;std.ArrayList from episode 22 (we use it as both a queue and a stack) and std.mem.tokenizeScalar from episode 5 for the exercise solutions;Learn Zig Series):Last episode ended on a promise: we had the graph sitting in memory in three shapes, we could ask it who-is-next-to-whom in optimal time, but we had not yet walked anywhere in it. I claimed there are exactly two fundamental 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 that the only difference between them is whether you pull the next vertex from the front or the back of the pending pile. Today we cash that in. And it is even better than I let on: BFS and DFS are so nearly the same algorithm that you can write them as one function with a single knob. But first -- the graph debt from episode 118, all three exercises, in real compilable code ;-)
Exercise 1 -- directed in-degree, out-degree, and a cycle hint. Out-degree is free: it is just the length of a vertex's own neighbour list, because in a directed graph addEdge(a, b) only appends b to a's list. In-degree is the harder direction -- nobody stores "who points at me", so you have to scan every vertex's list and count the arrows that land on v, which is an O(V + E) sweep of the whole graph. The hasCycleHint at the bottom leans on a real fact: a valid dependency order (a topological order) can only exist if some vertex has in-degree zero -- a starting point with nothing before it. If every vertex has something pointing at it, you are definitely stuck in a cycle. Note the word hint: in-degree-zero existing does not prove acyclicity (that comes later in the arc), it just rules out the obvious dead-lock. Here is the extended Graph from episode 118 with the three new methods:
const std = @import("std");
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 outDegree(self: *const Graph, v: usize) usize {
return self.adj.items[v].items.len; // trivial: length of v's own list
}
fn inDegree(self: *const Graph, v: usize) usize {
var count: usize = 0; // O(V + E): scan every list for arrows into v
for (self.adj.items) |list| {
for (list.items) |nb| {
if (nb == v) count += 1;
}
}
return count;
}
fn hasCycleHint(self: *const Graph) bool {
var v: usize = 0;
while (v < self.adj.items.len) : (v += 1) {
if (self.inDegree(v) == 0) return false; // a source exists -> no obvious deadlock
}
return true; // everyone has an in-edge -> must contain a cycle
}
};
test "in/out degree and the cycle hint" {
const gpa = std.testing.allocator;
var dag = try Graph.init(gpa, 4, true); // 0 -> 1 -> 2 -> 3, a clean chain
defer dag.deinit();
try dag.addEdge(0, 1);
try dag.addEdge(1, 2);
try dag.addEdge(2, 3);
try std.testing.expectEqual(@as(usize, 1), dag.outDegree(1));
try std.testing.expectEqual(@as(usize, 1), dag.inDegree(2));
try std.testing.expectEqual(@as(usize, 0), dag.inDegree(0));
try std.testing.expect(!dag.hasCycleHint()); // node 0 is a source
var cyclic = try Graph.init(gpa, 3, true); // 0 -> 1 -> 2 -> 0
defer cyclic.deinit();
try cyclic.addEdge(0, 1);
try cyclic.addEdge(1, 2);
try cyclic.addEdge(2, 0);
try std.testing.expect(cyclic.hasCycleHint()); // every node has an in-edge
}
Exercise 2 -- load a graph from text. Real graph datasets almost never arrive as pretty structs; they arrive as a text file, one "u v" edge per line. So fromEdgeText splits on newlines with std.mem.tokenizeScalar (which conveniently skips blank lines for us), splits each line on spaces to get the two vertex ids, parses them with std.fmt.parseInt, and feeds them into an undirected Graph. The lovely part is the check at the end: because we built it undirected, the handshake lemma from last episode must hold -- the sum of all degrees equals twice the number of lines we parsed.
fn fromEdgeText(gpa: std.mem.Allocator, n: usize, text: []const u8) !Graph {
var g = try Graph.init(gpa, n, false);
errdefer g.deinit(); // if a later line fails to parse, do not leak the graph
var lines = std.mem.tokenizeScalar(u8, text, '\n');
while (lines.next()) |line| {
var parts = std.mem.tokenizeScalar(u8, line, ' ');
const u_str = parts.next() orelse continue; // tolerate a stray blank line
const v_str = parts.next() orelse return error.MalformedEdge;
const u = try std.fmt.parseInt(usize, u_str, 10);
const v = try std.fmt.parseInt(usize, v_str, 10);
try g.addEdge(u, v);
}
return g;
}
test "parse an edge list from text and verify with the handshake lemma" {
const gpa = std.testing.allocator;
const text =
\\0 1
\\0 2
\\1 2
\\3 4
;
var g = try fromEdgeText(gpa, 5, text);
defer g.deinit();
var degree_sum: usize = 0;
for (0..5) |v| degree_sum += g.degree(v);
try std.testing.expectEqual(@as(usize, 8), degree_sum); // 4 edges * 2
try std.testing.expectEqual(@as(usize, 2), g.degree(0));
}
The errdefer g.deinit() is the detail that separates careful Zig from hopeful Zig: if line three has garbage in it and parseInt returns an error, we have already allocated the graph and appended two edges -- without the errdefer, that half-built graph leaks on the way out. errdefer fires only on the error path, so the happy path returns the graph to the caller untouched.
Exercise 3 -- convert an adjacency list to CSR and prove they agree. Last episode we built CSR (compressed sparse row) as the fast, static, cache-friendly representation, and I promised the pipeline that a real engine runs at load time: build the graph the easy way (adjacency list), then flatten it into CSR before you start traversing. toCsr does exactly that -- it counts degrees into an offsets array, prefix-sums them into row starts, then copies each neighbour into the flat targets array. The test then proves the two representations describe the same graph by comparing neighbour sets vertex by vertex (sorted first, because the flattening order need not match):
const Edge = struct { from: usize, to: usize };
const Csr = struct {
offsets: []usize,
targets: []usize,
gpa: std.mem.Allocator,
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]];
}
};
fn toCsr(self: *const Graph, gpa: std.mem.Allocator) !Csr {
const n = self.adj.items.len;
var total: usize = 0;
for (self.adj.items) |list| total += list.items.len;
const offsets = try gpa.alloc(usize, n + 1);
@memset(offsets, 0);
for (self.adj.items, 0..) |list, v| offsets[v + 1] = list.items.len;
for (0..n) |i| offsets[i + 1] += offsets[i]; // prefix sum -> row starts
const targets = try gpa.alloc(usize, total);
for (self.adj.items, 0..) |list, v| {
@memcpy(targets[offsets[v]..offsets[v + 1]], list.items);
}
return .{ .offsets = offsets, .targets = targets, .gpa = gpa };
}
test "adjacency list flattens to a CSR that agrees on every vertex" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 4, false);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(0, 2);
try g.addEdge(1, 3);
var csr = try toCsr(&g, gpa);
defer csr.deinit();
for (0..4) |v| {
const a = try gpa.dupe(usize, g.neighbors(v));
defer gpa.free(a);
const b = try gpa.dupe(usize, csr.neighbors(v));
defer gpa.free(b);
std.mem.sort(usize, a, {}, std.sort.asc(usize));
std.mem.sort(usize, b, {}, std.sort.asc(usize));
try std.testing.expectEqualSlices(usize, a, b);
}
}
Debt paid, and notice how the whole graph type from last episode carried straight over. Now, the walk ;-)
Here is the claim I want to earn. Every graph traversal that visits each reachable vertex exactly once has the same skeleton:
visited marker for every vertex so you never process one twice (this is what makes cycles harmless -- without it a loop of edges would spin forever).The only decision left is which end of the pile you pull from. Pull from the front and you get a queue -- first in, first out -- and the traversal spreads outward in rings: all the source's direct neighbours first, then everything two steps away, then three. That is breadth-first. Pull from the back and you get a stack -- last in, first out -- and the traversal dives down one path as far as it goes before it ever considers a sibling. That is depth-first. Same four steps, same visited array, same neighbour loop. One knob. That is the whole secret, and everything below is just the consequences of turning it.
Let's build BFS first, because the queue version has a superpower that DFS does not: in an unweighted graph, the order BFS discovers vertices is the shortest-path order. The first time you reach a vertex, you have reached it by the fewest possible edges, guaranteed -- because you exhausted everything at distance 1 before touching anything at distance 2. So in stead of a bare visited bool array, I will carry an i64 distance array where -1 doubles as "not visited yet". Reaching a vertex sets its distance to the parent's plus one:
fn bfs(gpa: std.mem.Allocator, g: *const Graph, source: usize) ![]i64 {
const n = g.adj.items.len;
const dist = try gpa.alloc(i64, n);
@memset(dist, -1); // -1 means "unvisited"
var queue: std.ArrayList(usize) = .empty;
defer queue.deinit(gpa);
dist[source] = 0;
try queue.append(gpa, source);
var head: usize = 0; // read cursor: everything before it is dequeued
while (head < queue.items.len) {
const v = queue.items[head];
head += 1;
for (g.neighbors(v)) |nb| {
if (dist[nb] == -1) { // first time we see it -> shortest distance
dist[nb] = dist[v] + 1;
try queue.append(gpa, nb);
}
}
}
return dist; // caller owns this and must free it
}
test "BFS distances are shortest hop counts, -1 for unreachable" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 6, false);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(0, 2);
try g.addEdge(1, 3);
try g.addEdge(2, 3);
try g.addEdge(3, 4);
// vertex 5 is left isolated on purpose
const dist = try bfs(gpa, &g, 0);
defer gpa.free(dist);
try std.testing.expectEqual(@as(i64, 0), dist[0]);
try std.testing.expectEqual(@as(i64, 1), dist[1]);
try std.testing.expectEqual(@as(i64, 2), dist[3]); // via 0->1->3 (or 0->2->3), both length 2
try std.testing.expectEqual(@as(i64, 3), dist[4]);
try std.testing.expectEqual(@as(i64, -1), dist[5]); // unreachable
}
Two implementation choices deserve a stare. First, the queue is an ArrayList with a head cursor instead of an actual ring buffer or a shifting deque. We never delete from the front -- we just advance head past the dequeued items. This is dead simple, allocation-cheap (one growable array, doubled as needed), and perfectly fine for a one-shot traversal that throws the queue away at the end. If you were running BFS millions of times in a hot loop you might reuse a pre-sized ring buffer (episode 113) to avoid the regrowth, but for correctness and clarity the cursor wins. Second, and this is the subtle one that trips people up: we mark a vertex visited (set its distance) at enqueue time, not dequeue time. If you wait until you pop a vertex to mark it, the same vertex can get pushed onto the queue several times before it is ever popped -- once by each neighbour that discovers it -- and you both waste work and risk assigning it a wrong distance. Mark-on-enqueue means each vertex enters the queue exactly once. Remember that; it is the number-one BFS bug.
A distance of 3 is nice, but usually you want the route: which vertices, in order, get you from source to target in those three hops. The fix is one extra array. Alongside dist, keep a parent array: when vertex v first discovers neighbour nb, record parent[nb] = v. Then to rebuild the path you start at the target and walk parents backward to the source, collecting vertices, and reverse the list at the end:
fn bfsShortestPath(gpa: std.mem.Allocator, g: *const Graph, source: usize, target: usize) !?[]usize {
const n = g.adj.items.len;
const parent = try gpa.alloc(i64, n);
defer gpa.free(parent);
@memset(parent, -1);
const visited = try gpa.alloc(bool, n);
defer gpa.free(visited);
@memset(visited, false);
var queue: std.ArrayList(usize) = .empty;
defer queue.deinit(gpa);
visited[source] = true;
try queue.append(gpa, source);
var head: usize = 0;
while (head < queue.items.len) {
const v = queue.items[head];
head += 1;
if (v == target) break; // found it; parents are all we need now
for (g.neighbors(v)) |nb| {
if (!visited[nb]) {
visited[nb] = true;
parent[nb] = @intCast(v);
try queue.append(gpa, nb);
}
}
}
if (!visited[target]) return null; // no route exists
var path: std.ArrayList(usize) = .empty;
errdefer path.deinit(gpa);
var cur: i64 = @intCast(target);
while (cur != -1) : (cur = parent[@intCast(cur)]) {
try path.append(gpa, @intCast(cur));
}
std.mem.reverse(usize, path.items); // we collected target-first
return try path.toOwnedSlice(gpa);
}
test "shortest path reconstruction returns the actual route" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 6, false);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(1, 2);
try g.addEdge(2, 5);
try g.addEdge(0, 3);
try g.addEdge(3, 4);
try g.addEdge(4, 5); // two routes to 5, both length 3
const maybe = try bfsShortestPath(gpa, &g, 0, 5);
try std.testing.expect(maybe != null);
const path = maybe.?;
defer gpa.free(path);
try std.testing.expectEqual(@as(usize, 0), path[0]); // starts at source
try std.testing.expectEqual(@as(usize, 5), path[path.len - 1]); // ends at target
try std.testing.expectEqual(@as(usize, 4), path.len); // 3 edges -> 4 vertices
}
I switched to a separate visited bool plus an i64 parent here, which is slightly more honest about intent than reusing the distance array as a visited flag -- and note toOwnedSlice hands the caller a right-sized slice, transferring ownership out of the ArrayList so the errdefer no longer applies once we return. This is the beating heart of every maze solver, every "fewest transfers" transit router, every word-ladder puzzle. Unweighted shortest path is just BFS with a parent array, nothing more.
Now turn the knob. Swap the queue for a stack and BFS becomes DFS. The structure is so close it is almost cheeky -- append to the pile the same way, but pull from the back instead of the front:
fn dfsIterative(gpa: std.mem.Allocator, g: *const Graph, source: usize) ![]usize {
const n = g.adj.items.len;
const visited = try gpa.alloc(bool, n);
defer gpa.free(visited);
@memset(visited, false);
var order: std.ArrayList(usize) = .empty;
errdefer order.deinit(gpa);
var stack: std.ArrayList(usize) = .empty;
defer stack.deinit(gpa);
try stack.append(gpa, source);
while (stack.items.len > 0) {
const v = stack.items[stack.items.len - 1]; // peek the back
stack.items.len -= 1; // ...and pop it
if (visited[v]) continue; // may have been queued twice; skip duplicates
visited[v] = true;
try order.append(gpa, v);
for (g.neighbors(v)) |nb| {
if (!visited[nb]) try stack.append(gpa, nb);
}
}
return try order.toOwnedSlice(gpa);
}
test "iterative DFS visits every reachable vertex once" {
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, 3);
try g.addEdge(2, 4);
const order = try dfsIterative(gpa, &g, 0);
defer gpa.free(order);
try std.testing.expectEqual(@as(usize, 5), order.len); // all reachable
try std.testing.expectEqual(@as(usize, 0), order[0]); // starts at source
// every vertex appears exactly once
var seen = [_]bool{false} ** 5;
for (order) |v| {
try std.testing.expect(!seen[v]);
seen[v] = true;
}
}
One difference from BFS is worth calling out. Here I mark visited at pop time, not push time, and I add the if (visited[v]) continue guard. Why the asymmetry? Because with a stack a vertex can legitimately be pushed more than once before it is ever popped -- vertex 3 might be reachable from both 1 and 2, and both push it. Marking on pop with a skip-if-already-visited guard is the clean way to handle that. You can mark on push like BFS, and it is a hair more efficient (fewer stack entries), but the pop-time version maps more directly onto the recursive form we are about to write -- and honestly it is the shape you will see in most textbooks. Both are correct; pick one and be consistent.
DFS has a second face that BFS simply does not: because "dive deep, then back up" is exactly what the call stack does, you can write DFS with no explicit stack at all -- the function calling itself IS the stack. It is arguably the most elegant few lines in this whole episode:
fn dfsRecursive(g: *const Graph, v: usize, visited: []bool, order: *std.ArrayList(usize), gpa: std.mem.Allocator) !void {
visited[v] = true;
try order.append(gpa, v);
for (g.neighbors(v)) |nb| {
if (!visited[nb]) try dfsRecursive(g, nb, visited, order, gpa);
}
}
test "recursive DFS visits the same set as the iterative version" {
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, 3);
try g.addEdge(2, 4);
const visited = try gpa.alloc(bool, 5);
defer gpa.free(visited);
@memset(visited, false);
var order: std.ArrayList(usize) = .empty;
defer order.deinit(gpa);
try dfsRecursive(&g, 0, visited, &order, gpa);
try std.testing.expectEqual(@as(usize, 5), order.items.len);
try std.testing.expectEqual(@as(usize, 0), order.items[0]);
}
Gorgeous, isn't it? And a loaded gun. The call stack is a fixed, small resource -- typically eight megabytes -- and each recursive call eats a frame. On a friendly little graph that is nothing. On a pathological one -- say a single chain of a million vertices, 0 -> 1 -> 2 -> ... -> 999999, which a directed dependency graph or a linked-list-shaped social graph can absolutely be -- the recursion goes a million frames deep and Zig crashes with a stack overflow. There is no try you can write to catch that; a blown call stack is not a Zig error, it is a hard segfault. This is the reason the explicit-stack version exists: it moves the pending pile onto the heap, where it can grow to gigabytes, and it never touches the call-stack depth at all. Rule of thumb from real systems work: recursion is fine for graphs whose depth you can bound (a balanced tree, a small mesh), and a trap the moment an adversary or a big dataset controls the shape. When in doubt, use the iterative one. Having said that, the recursive form is unbeatable for readability and for the classic pre-order/post-order bookkeeping that topological sorting needs -- which is a hint about where we are headed, but I am getting ahead of myself.
Traversal is rarely the goal in itself -- it is the engine other things ride on. Two classics fall out immediately. The first is connected components: how many separate islands does this graph have? A single BFS or DFS from a source reaches exactly the vertices in that source's island and no others. So to count and label all components, you loop over every vertex, and each time you find one not yet visited, you launch a fresh traversal from it and stamp everything it reaches with a new component id:
fn connectedComponents(gpa: std.mem.Allocator, g: *const Graph) ![]usize {
const n = g.adj.items.len;
const comp = try gpa.alloc(usize, n);
@memset(comp, std.math.maxInt(usize)); // maxInt = "not assigned yet"
var next_id: usize = 0;
var stack: std.ArrayList(usize) = .empty;
defer stack.deinit(gpa);
for (0..n) |start| {
if (comp[start] != std.math.maxInt(usize)) continue; // already in a component
try stack.append(gpa, start); // flood-fill this island
comp[start] = next_id;
while (stack.items.len > 0) {
const v = stack.items[stack.items.len - 1];
stack.items.len -= 1;
for (g.neighbors(v)) |nb| {
if (comp[nb] == std.math.maxInt(usize)) {
comp[nb] = next_id;
try stack.append(gpa, nb);
}
}
}
next_id += 1;
}
return comp; // comp[v] = which island v belongs to; next_id = total count
}
test "connected components labels each island distinctly" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 6, false);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(1, 2); // island A: {0,1,2}
try g.addEdge(3, 4); // island B: {3,4}
// vertex 5 alone: island C
const comp = try connectedComponents(gpa, &g);
defer gpa.free(comp);
try std.testing.expectEqual(comp[0], comp[2]); // same island
try std.testing.expect(comp[0] != comp[3]); // different islands
try std.testing.expect(comp[3] != comp[5]);
try std.testing.expect(comp[0] != comp[5]);
}
That "loop over all vertices, launch a traversal from each unvisited one" pattern is worth burning into memory -- it is how you make any single-source traversal cover a possibly-disconnected graph. The second payoff is cycle detection in an undirected graph. During a DFS, if you ever reach an already-visited vertex that is not the one you just came from, you have found a second route to it -- and two routes between two vertices means a cycle. The "not the parent" check is the whole trick: in an undirected graph every edge looks like a back-edge to your immediate predecessor (you can always walk back the way you came), so you must exclude the parent to avoid a false positive.
fn hasCycleUndirected(gpa: std.mem.Allocator, g: *const Graph) !bool {
const n = g.adj.items.len;
const visited = try gpa.alloc(bool, n);
defer gpa.free(visited);
@memset(visited, false);
// iterative DFS carrying each vertex's parent alongside it
const Frame = struct { v: usize, parent: i64 };
var stack: std.ArrayList(Frame) = .empty;
defer stack.deinit(gpa);
for (0..n) |start| {
if (visited[start]) continue;
try stack.append(gpa, .{ .v = start, .parent = -1 });
while (stack.items.len > 0) {
const f = stack.items[stack.items.len - 1];
stack.items.len -= 1;
if (visited[f.v]) return true; // reached an already-seen vertex -> cycle
visited[f.v] = true;
for (g.neighbors(f.v)) |nb| {
if (@as(i64, @intCast(nb)) == f.parent) continue; // ignore the edge back
if (!visited[nb]) try stack.append(gpa, .{ .v = nb, .parent = @intCast(f.v) });
}
}
}
return false;
}
test "cycle detection tells a tree from a graph with a loop" {
const gpa = std.testing.allocator;
var tree = try Graph.init(gpa, 4, false); // a tree has no cycle
defer tree.deinit();
try tree.addEdge(0, 1);
try tree.addEdge(1, 2);
try tree.addEdge(1, 3);
try std.testing.expect(!try hasCycleUndirected(gpa, &tree));
var looped = try Graph.init(gpa, 4, false);
defer looped.deinit();
try looped.addEdge(0, 1);
try looped.addEdge(1, 2);
try looped.addEdge(2, 0); // 0-1-2-0 closes a triangle
try std.testing.expect(try hasCycleUndirected(gpa, &looped));
}
Here is where the "one algorithm, one knob" idea earns its keep as a test. BFS and DFS visit vertices in completely different orders -- that is the entire point of them -- but they must always agree on which vertices are reachable from a source, because reachability is a property of the graph, not of the walking discipline. That is a perfect invariant for property-based testing (the same discipline we used on binary search and on the graph itself): throw hundreds of random graphs at both algorithms and assert the reachable sets are identical every single time.
test "property: BFS and DFS reach exactly the same vertex set" {
const gpa = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xF00D);
const rand = prng.random();
var round: usize = 0;
while (round < 200) : (round += 1) {
const n = rand.intRangeAtMost(usize, 1, 25);
var g = try Graph.init(gpa, n, false);
defer g.deinit();
const m = rand.intRangeAtMost(usize, 0, 40);
for (0..m) |_| {
const a = rand.uintLessThan(usize, n);
const b = rand.uintLessThan(usize, n);
if (a == b) continue;
try g.addEdge(a, b);
}
const source = rand.uintLessThan(usize, n);
const dist = try bfs(gpa, &g, source);
defer gpa.free(dist);
const order = try dfsIterative(gpa, &g, source);
defer gpa.free(order);
// mark which vertices DFS reached
const dfs_seen = try gpa.alloc(bool, n);
defer gpa.free(dfs_seen);
@memset(dfs_seen, false);
for (order) |v| dfs_seen[v] = true;
// BFS reached v iff dist[v] != -1; the two sets must match exactly
for (0..n) |v| {
const bfs_reached = dist[v] != -1;
try std.testing.expectEqual(bfs_reached, dfs_seen[v]);
}
}
}
Two hundred random graphs, random sources, and every time the BFS-reachable set (distance not -1) must be byte-for-byte the DFS-reachable set. If a bug ever creeps into either -- an off-by-one in the queue cursor, a missing visited check in the stack -- this test lights up immediately, and because it all runs on std.testing.allocator, any leaked queue or stack fails the round too. One invariant, hundreds of graphs, far more coverage than any hand-drawn example. Wowzers, I love this style of test ;-)
In C, BFS and DFS are the same two loops, but you build the queue and the stack yourself -- typically a fixed int array plus head/tail indices for the queue, and a plain array plus a top index for the stack. The visited set is a calloc'd char array. It works and it is fast, but there is no testing.allocator looking over your shoulder: forget to free the queue on an early return and it is a silent leak, and the recursive DFS blows the C call stack exactly the way Zig's does, just with even less ceremony about telling you why.
In Rust, you would reach for std::collections::VecDeque as the BFS queue (push_back / pop_front) and a Vec as the DFS stack, with a vec![false; n] for visited. The borrow checker actually pushes you toward the vertex-as-index design we have been using all series -- you cannot easily hold a mutable reference to the graph and to a node inside it at once, so everybody passes around usize indices and indexes into flat vectors, which is precisely our Zig shape. Idiomatic Rust graph traversal and idiomatic Zig graph traversal are near-identical line for line; the difference is Rust frees the queue for you when it drops.
In Go, the queue is usually a slice you append to and reslice (queue = queue[1:] to dequeue), the stack is a slice with append and a reslice-off-the-end to pop, and visited is a []bool or a map[int]bool for sparse ids. The garbage collector means you never write a defer queue.deinit -- convenient, though it is also why a Go service that accidentally holds references to old traversal state can leak in ways the GC cannot save you from. Go's goroutines tempt people into parallel BFS, which is a genuinely hard problem (the shared visited set needs careful synchronisation, episode 30 territory) and almost always not worth it below enormous graph sizes.
Our Zig versions sit where Zig always sits: the same handful of ideas as everyone else, the cache-friendly index-based layout Rust arrives at by necessity, but with explicit control of every allocation the way C insists on -- and the testing.allocator catching the leaks C would let slide. Same two walks in four languages, and in every one of them the queue-versus-stack knob is the entire story. Bam, jonguh ;-)
Multi-source BFS. Modify bfs to accept a slice of source vertices instead of one, seeding the queue with all of them at distance 0 up front. The result: dist[v] becomes the distance from the nearest source. This is how you compute, in one pass, "how far is every cell from the closest exit" in a grid, or "how many hops to the nearest server" in a network. Test it with two sources and confirm a vertex between them gets the smaller of the two distances.
Bipartite check via BFS colouring. A graph is bipartite if you can two-colour its vertices so that no edge joins two vertices of the same colour (think: can these people be split into two teams with no internal rivalries?). Run a BFS and colour each vertex the opposite of the vertex that discovered it; if you ever find an edge between two same-coloured vertices, it is not bipartite. Return bool and test it on an even cycle (bipartite) and an odd cycle like a triangle (not).
Detect a cycle in a directed graph. The undirected trick (ignore the parent) does not work for directed graphs -- there you need three states per vertex: unvisited, "in the current recursion stack", and "fully finished". A directed cycle exists if, during DFS, you reach a vertex that is currently in the recursion stack (a true back-edge), not merely one that is finished. Implement hasCycleDirected and test it on a directed acyclic chain versus a directed loop. (This three-colour idea is the exact machinery behind the thing we build next.)
We can now walk a graph two ways, find shortest paths when every edge counts the same, split a graph into islands, and spot a loop. But look back at that last exercise, and back at the hasCycleHint we wrote at the very top of this episode: both are circling the same question -- given a directed graph of dependencies, is there a valid order to do the work, one where nothing comes before the things it depends on? Build systems asking "what do I compile first", package managers resolving install order, spreadsheets recalculating cells: they all need to flatten a directed acyclic graph into a straight line that respects every arrow. It turns out DFS, with one small piece of post-order bookkeeping, hands you that ordering almost for free -- and if no such ordering exists, the very same machinery tells you exactly why. That linearisation is where we go next ;-)
Thanks for reading, and I will see you in the next one!
@scipio