Graphs: representation, BFS and DFS

A graph is vertices plus edges between them — road networks, dependencies, friendships, grid mazes, state machines. Almost every graph algorithm is built on one of two traversals: breadth-first search (a queue; explores by distance) and depth-first search (a stack; explores one path as far as it goes). This lesson covers how to store graphs so those traversals are fast, and how to write both without recursion blowing the stack.

1. Storing a graph

Number the vertices 0 … n-1. Three common representations:

Real graphs are usually sparse (E ≈ a few × V), so adjacency lists win: a traversal touches each list once, for O(V + E) total. A matrix forces O(V) work per vertex just to find its neighbours — O(V²) per traversal, and a million-vertex matrix needs 10¹² cells.

Directed edges u → v go into u's list only; an undirected edge u – v goes into both. Graphs can have self-loops (u – u) and parallel edges (the same pair twice); code should not assume either away.

#include <cstddef>
#include <print>
#include <vector>

int main() {
    std::size_t n = 5;
    std::vector<std::vector<std::size_t>> adj(n);
    auto add = [&](std::size_t u, std::size_t v) {  // undirected
        adj[u].push_back(v);
        if (u != v) adj[v].push_back(u);
    };
    add(0, 1);
    add(0, 2);
    add(1, 2);
    add(3, 4);
    for (std::size_t u = 0; u < n; ++u) std::println("{}: {}", u, adj[u]);
}

CSR (compressed sparse row) is the cache-friendly version for graphs that don't change: one flat targets array holding every list back to back, and an offsets array where u's neighbours are targets[offsets[u] .. offsets[u+1]). Two allocations instead of V, and traversals stream through memory.

2. BFS: layer by layer

BFS visits vertices in order of their distance (number of edges) from a source. Its invariant:

the queue holds vertices of distance d followed by vertices of distance d + 1 — never anything else.

So when a vertex is first discovered, it's discovered along a shortest path. That's why BFS computes shortest paths in unweighted graphs.

Worked example: distances and the path itself

#include <algorithm>
#include <cstddef>
#include <print>
#include <queue>
#include <vector>

using Adj = std::vector<std::vector<std::size_t>>;

int main() {
    // 0 - 1 - 2 - 3 - 4, plus a shortcut 1 - 4
    Adj adj(5);
    auto add = [&](std::size_t u, std::size_t v) { adj[u].push_back(v); adj[v].push_back(u); };
    add(0, 1); add(1, 2); add(2, 3); add(3, 4); add(1, 4);

    constexpr std::size_t none = static_cast<std::size_t>(-1);
    std::vector<int> dist(adj.size(), -1);
    std::vector<std::size_t> parent(adj.size(), none);
    std::queue<std::size_t> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        std::size_t u = q.front();
        q.pop();
        for (std::size_t v : adj[u]) {
            if (dist[v] == -1) {        // mark when *pushing*, so v enters the queue once
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    std::println("distances: {}", dist);

    std::vector<std::size_t> path;      // walk parents back from the target
    for (std::size_t v = 4; v != none; v = parent[v]) path.push_back(v);
    std::ranges::reverse(path);
    std::println("path 0 → 4: {}", path);
}

Line by line:

• dist[v] == -1 doubles as the visited flag. Mark when you push, not when you pop: otherwise a vertex with many already-queued neighbours is pushed many times.
• parent[v] = u records the edge that discovered v. Following parents from the target leads back to the source along a shortest path; reverse it.
• Each vertex is pushed once and each list scanned once: O(V + E).

Use std::queue (a deque underneath). A std::vector with erase(begin()) is a classic trap: every pop shifts the whole frontier, which makes BFS O(V²) on wide graphs.

Multi-source BFS: push several sources at distance 0 before the loop ("distance to the nearest hospital"). 0-1 BFS (a preview): when edges weigh 0 or 1, push 0-edges to the front of a deque and 1-edges to the back; the deque stays sorted by distance. General weights need Dijkstra (Level 7).

3. DFS: one path at a time

DFS goes as deep as possible before backing up. Recursively it is three lines — and that's the trap:

void dfs(std::size_t u) {           // fine for a 100-vertex graph…
    seen[u] = true;
    for (auto v : adj[u]) if (!seen[v]) dfs(v);
}

On a path of 200,000 vertices that's 200,000 nested calls. Each frame costs dozens to hundreds of bytes (more without optimisation or under ASan), and the default stack is 8 MiB: the program crashes. Any DFS over input-sized graphs should use an explicit stack:

#include <cstddef>
#include <print>
#include <vector>

int main() {
    std::size_t n = 200'000;  // a long path: far too deep for recursion
    std::vector<std::vector<std::size_t>> adj(n);
    for (std::size_t i = 0; i + 1 < n; ++i) {
        adj[i].push_back(i + 1);
        adj[i + 1].push_back(i);
    }
    std::vector<bool> seen(n, false);
    std::vector<std::size_t> stack{0};
    seen[0] = true;
    std::size_t visited = 0;
    while (!stack.empty()) {
        std::size_t u = stack.back();
        stack.pop_back();
        ++visited;
        for (std::size_t v : adj[u])
            if (!seen[v]) {
                seen[v] = true;
                stack.push_back(v);
            }
    }
    std::println("visited {} vertices without recursion", visited);
}

This "mark on push" stack version visits everything a DFS would, but not in exactly the recursive order. That's fine for reachability questions — components, flood fill. When you need the real DFS structure (when did we finish u?), keep (vertex, next-neighbour index) pairs on the stack: look at the top; if its neighbours are used up, u is finished — pop it; otherwise advance its index and push that neighbour. That replays recursion exactly, finish times included.

Discovery and finish times, edge types

In a recursive-order DFS on a directed graph, each edge u → v is one of:

• tree edge — v is new; DFS descends into it.
• back edge — v is an ancestor still on the current path. Back edges are exactly the cycles.
• forward / cross edge — v is already finished: a descendant reached another way, or a different branch.

That's why cycle detection uses three colours: white (unseen), grey (on the current path), black (finished). An edge to grey is a back edge → cycle. An edge to black is not: in the diamond 0→1→3, 0→2→3, vertex 3 is reached twice with no cycle at all.

4. Questions every traversal answers

• Connected components (undirected): for each vertex not yet labelled, start a traversal and give everything it reaches the next label. O(V + E) over all starts combined.
• Undirected cycles: an edge to an already-seen vertex that isn't the one you came from. (Careful: with parallel edges, "the one you came from" is a specific edge, not a vertex — two parallel edges u–v are a cycle.)
• Directed cycles: three colours, as above.
• Bipartite (two-colourable, i.e. no odd cycle): BFS and give each layer alternating colours; any edge within one colour — including a self-loop — means no. Do it for every component.

Faded example: bipartite check

Fill in the two marked lines, then check yourself against the answer.

std::vector<int> side(n, -1);
for (std::size_t s = 0; s < n; ++s) {
    if (side[s] != -1) continue;
    side[s] = 0;
    std::queue<std::size_t> q;
    q.push(s);
    while (!q.empty()) {
        auto u = q.front(); q.pop();
        for (auto v : adj[u]) {
            if (side[v] == -1) { /* ??? */ }
            else if (/* ??? */) return false;
        }
    }
}
return true;

5. Grids are graphs

A maze or map stored as vector<string> is a graph whose vertices are cells and whose edges join up/down/left/right neighbours (or 8 directions). You don't build an adjacency list — you compute neighbours on the fly, checking bounds first:

#include <cstddef>
#include <print>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> grid{"##.", ".#.", "..#"};
    std::size_t rows = grid.size(), cols = grid[0].size();
    std::vector<std::vector<bool>> seen(rows, std::vector<bool>(cols, false));
    int islands = 0;
    for (std::size_t r = 0; r < rows; ++r)
        for (std::size_t c = 0; c < cols; ++c) {
            if (grid[r][c] != '#' || seen[r][c]) continue;
            ++islands;
            std::vector<std::pair<std::size_t, std::size_t>> stack{{r, c}};
            seen[r][c] = true;
            while (!stack.empty()) {
                auto [y, x] = stack.back();
                stack.pop_back();
                auto visit = [&](std::size_t ny, std::size_t nx) {
                    if (grid[ny][nx] == '#' && !seen[ny][nx]) {
                        seen[ny][nx] = true;
                        stack.push_back({ny, nx});
                    }
                };
                if (y > 0) visit(y - 1, x);          // test before subtracting:
                if (y + 1 < rows) visit(y + 1, x);   // y - 1 on unsigned 0 wraps
                if (x > 0) visit(y, x - 1);
                if (x + 1 < cols) visit(y, x + 1);
            }
        }
    std::println("{} islands", islands);  // the diagonal cell is its own island
}

The classic bugs here are y + 1 <= rows (one row too far) and y - 1 on an unsigned y == 0, which wraps to a huge index. Both read out of bounds.

Summary

• Store sparse graphs as adjacency lists; traversals are then O(V + E).
• BFS (queue): distances and shortest paths in unweighted graphs; mark vertices when pushing; record parents to rebuild paths.
• DFS (stack): components, flood fill, cycles. Never recurse once per vertex on input-sized graphs — use an explicit stack; keep (vertex, index) pairs when finish order matters.
• Directed cycles need white/grey/black; only edges to grey vertices close cycles.
• Bipartite = BFS 2-colouring of every component; self-loops fail it.
• Grids: neighbours computed on the fly; check bounds before indexing.