Representing a Graph Before Traversing It

A graph models entities as vertices and relationships as edges. Friends, roads, dependencies, and links all fit this shape.

Most decisions get made before the first traversal runs. Directed or undirected. Weighted or unweighted. Dense or sparse. The representation you pick sets your memory ceiling. The algorithm then sets which questions stay cheap.

This article covers both halves in order: represent first, traverse second.

Lists fit sparse graphs, matrices fit dense ones

An adjacency list stores each vertex's neighbors in its own list. An undirected graph with V vertices and E edges stores 2E references plus one list header per vertex.

An adjacency matrix stores a V by V grid with one cell per pair. Edge tests read a single cell in O(1). The price is quadratic memory.

Concrete numbers settle the choice for a large sparse graph:

vertices = 1,000,000     edges = 10,000,000
 
adjacency list:    10^6 x 8 B + 2 x 10^7 x 8 B   ~  168 MB
adjacency matrix:  10^6 x 10^6 cells             ~  4 TB at 1 byte per cell

The matrix does not fit in RAM. It is not slightly slower; it is impossible. Matrices win only for genuinely dense graphs, such as all-pairs distances over 500 cities, where O(1) edge tests beat scanning neighbor lists.

Social graphs, road networks, and dependency graphs are sparse. They get lists. Dense similarity matrices and Floyd-Warshall tables get matrices.

Breadth-first search expands in rings

Breadth-first search, or BFS, visits vertices in order of distance from the start. It uses a queue: new vertices wait at the back while the front expands. The first visit to a vertex therefore uses the fewest edges possible.

The total cost is O(V + E). Each vertex enters the queue once. Each edge gets examined once. No work repeats.

The same traversal in three languages:

#include <queue>
#include <vector>
#include <unordered_map>
// Walk a graph in rings and record each vertex's distance in edges.
// Every vertex enters the queue once: total cost O(V + E).
std::unordered_map<int, int> bfs(const std::vector<std::vector<int>>& g, int start) {
    // depth[v] holds the fewest edges from start to v.
    std::unordered_map<int, int> depth{{start, 0}};
    std::queue<int> q; // vertices waiting for expansion, nearest first
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop(); // expand the nearest waiting vertex
        for (int w : g[v]) { // check every neighbor of v
            if (!depth.count(w)) { // first sighting: fewest edges found
                depth[w] = depth[v] + 1; // one edge farther than v
                q.push(w); // wait for its own expansion turn
            }
        }
    }
    return depth;
}

One detail decides correctness and memory. Mark a vertex visited when it enters the queue, not when it leaves. Late marking lets a vertex with five inbound edges queue five times. On a million-node graph that duplication exhausts memory.

BFS finds fewest-edges paths. That equals cheapest paths only when every edge costs the same. Weighted roads need a different tool.

Depth-first search follows each path to its end

Depth-first search, or DFS, goes deep before it goes wide. It follows one neighbor chain to its end, backtracks, and tries the next branch. An explicit stack or the call stack tracks the way back.

DFS answers structural questions. It detects cycles. It orders tasks topologically so dependencies run first. It finds strongly connected components and tests reachability.

Two traps await beginners. Deep recursion overflows the call stack: a chain of a million vertices needs an explicit stack structure, not nested calls. Visited marking must also happen at push time, or the same vertex queues repeatedly through many inbound edges.

Recursion suits DFS on shallow trees and small graphs because the code mirrors the structure. Production crawlers and build systems use explicit stacks because input depth is unmeasured and untrusted.

Weights choose the shortest-path tool

Edge weights change which algorithm is correct. Three tools cover the cases:

Dijkstra's algorithm finalizes vertices in order of distance. Its greedy step assumes no later path beats a finalized one. A negative edge breaks that assumption: a finished vertex can still get cheaper. Running Dijkstra over a discount or a rebate credit returns a path that looks cheapest only because the algorithm stopped too early.

Bellman-Ford tolerates negatives by relaxing all edges V − 1 times. It runs slower but reports negative cycles instead of wrong answers. Use it when weights come from untrusted or adjusted data.

Two more hazards recur in production. Initializing distances to the maximum integer and then adding a weight overflows into negative values, and Dijkstra "discovers" a path costing minus two billion. Use a wider type or a sentinel the arithmetic cannot cross. Reusing a visited array across many sources without clearing costs O(V) per run; stamping entries with the query ID avoids the wipe.

Where graphs run and what to read next

Navigation apps run Dijkstra over road graphs with millions of vertices. Build tools topologically sort dependency graphs before compiling. Social networks fan BFS outward for friend suggestions. Package managers detect cycles before installs.

The workflow stays constant. Model the entities and relationships. Pick the representation by density. Match the traversal to the weights. Validate the preconditions on real data.

Watch the graph algorithms trace to see a traversal execute. Follow the graph flow for the representation decision. Then compare trees and heaps for the hierarchical special case of graphs.