Graphs

What is a Graph

A graph is a set of nodes plus a set of edges connecting them. That is the whole definition. Everything else — direction, weight, cycles — is a variation on those two sets.

Every structure so far has been about storing values. A graph is about relationships between values. The nodes are the things; the edges are how they relate.

This distinction matters: a graph is an abstract data type (ADT), not a concrete data structure. It defines what you can ask — add a node, connect two nodes, list a node's neighbors — but says nothing about how any of it is stored. The two concrete structures that honor that contract are the adjacency list and the adjacency matrix, and choosing between them is the single most consequential decision you make about a graph. That choice is what most of this article is about.

Note also what a graph is not: it has no first element, no last element, no order. A linked list is a graph where every node has exactly one neighbor; a tree is a graph with no cycles and one root. Graphs are the general case, and every structure in this series so far is a graph with rules bolted on.

The problem previous structures couldn't solve

Every structure so far imposes a shape on your data, and each shape has a matching question it answers well.

Arrays index by position. Position is a useful relationship when your data is genuinely sequential, but "user 4 is next to user 5" says nothing about whether they know each other.

Linked lists chain one node to the next. That's a relationship — but exactly one per node, always in one direction. You can't express "this station connects to three other stations."

Hash tables map a key to a value in O(1). That's the closest fit among the flat structures, and it's why graphs are usually built on one. But a hash table on its own stores key → value, not key → other keys.

Trees get closest of all, and the last five articles were variations on them. A tree finally lets one node point at many — but it pays for that with two restrictions it never relaxes: every node has exactly one parent, and there are no cycles. Those two are what make a tree's guarantees possible, and they are precisely what real relationships violate.

What none of them can express is many-to-many with cycles. A person has many friends, each of whom has many friends, and follow those links far enough and you come back to where you started. That's the structure graphs exist for — and dropping a tree's two restrictions is the whole of what a graph is.

Nodes, edges, and the vocabulary

Graphs come with more vocabulary than any structure so far. All of it describes the same two sets, so the fastest way through is to keep the same six nodes and change one thing at a time.

Directed vs undirected

In an undirected graph, an edge is mutual: if A connects to B, then B connects to A. Facebook friendship works this way — there's no such thing as a one-way friend.

In a directed graph (or digraph), each edge has a direction. A points to B says nothing about whether B points to A. Twitter follows work this way, as do web links, task dependencies, and function calls.

Direction changes what the structure stores, not just what it means. An undirected edge is recorded twice — once in each endpoint's neighbor list — while a directed edge is recorded once. That doubling is why an undirected adjacency list costs 2E slots rather than E.

In a directed graph each node has two counts: in-degree (edges arriving) and out-degree (edges leaving). D above has in-degree 2 and out-degree 0.

Weighted vs unweighted

An edge can carry a number: distance, cost, capacity, latency, similarity. A graph whose edges carry numbers is weighted.

Structurally, a weight is just a second value stored alongside each edge. In an adjacency list the neighbor entry becomes a small struct instead of a bare id; in a matrix the cell holds a number instead of a bool, with some sentinel — math.MaxInt, or 0 when zero can't be a legitimate weight — standing for "no edge."

That caption is what makes weights worth the extra field: A–C–D is two edges, the same as A–B–D, but it costs more. Once edges have different costs, "fewest edges" and "cheapest route" become different questions.

Degree, path, and cycle

A node's degree is how many edges touch it. A path is a sequence of nodes where each consecutive pair is connected. A simple path never repeats a node. A cycle is a path that ends where it began.

Degree is the number that decides how expensive a node is to work with: an adjacency list answers "who are this node's neighbors" in time proportional to its degree, so a high-degree node is a slow node. In a social graph that's the celebrity problem — a few accounts with millions of edges dominate the cost of everything.

Cycles are what separate a graph from a tree. Because D is reachable from A two different ways, there is no single parent relationship to lean on, and no guarantee that following edges ever ends. A graph with direction and no cycles is a DAG — a directed acyclic graph — which is the shape dependency data takes.

Connected, disconnected, and components

A graph is connected if there's a path between every pair of nodes. If not, it splits into connected components — islands with no edges between them.

G matters for the representation even though nothing points at it. An adjacency list still needs an entry for it — that's the V in O(V + E) — and a matrix still allocates its whole row and column. A node with no edges costs you something in both layouts, which is why the node count is never irrelevant.

Representing a Graph in memory

Two structures dominate, and the choice between them is a trade of space against lookup speed.

Adjacency list

Store, for each node, a list of its neighbors. In Go that's a map from node to slice of nodes.

For the graph above, the adjacency list is:

Each undirected edge appears twice — once from each end. A–B shows up in A's list and in B's. That's not redundancy to eliminate; it's what makes "list B's neighbors" as fast as "list A's."

Here's the type and its use. The usage is the point; the implementation is one tab over.

The space cost is O(V + E) — one map entry per node, one slice element per edge-end. For most real graphs that's small, because most real graphs are sparse: a Facebook user has hundreds of friends, not two billion.

Adjacency matrix

Store a V × V grid where cell [i][j] says whether an edge runs from i to j.

Two things to read off it. The matrix is symmetric across the diagonal, because the graph is undirected — for a digraph it wouldn't be. And it's mostly zeros: 12 of 36 cells carry an edge, and that ratio only gets worse as the graph grows.

Which one to use

A graph is dense when E approaches V², and sparse otherwise. And the crossover is exact rather than a matter of taste: an undirected adjacency list holds V + 2E slots, so on a complete graph, where E = V(V−1)/2, that comes to V + V(V−1) — precisely V², the matrix's cell count.

So the list is smaller for every graph that isn't complete, ties when it is, and only loses in practice because its slots are fatter: a slice header and a map bucket cost far more per entry than one byte in a grid. That's the real rule — a matrix wins when the graph is near-complete, small, or when hasEdge is your hot path, and a list wins everywhere else.

In practice that means adjacency lists win almost always, because the graphs people actually have — road networks, social graphs, dependency trees, the web — are all sparse.

Try it yourself

Two ways to edit the graph: click a line in the diagram to cut that edge, or click any matrix cell to toggle one. Either way, watch all three views move together — the diagram, the adjacency list, and the two space counters.

That the matrix works as a control at all is the point worth noticing: a cell is the question "is there an edge between these two," so answering it differently and editing the graph are the same action. The adjacency list has no cell to click for an edge that doesn't exist, which is exactly why it costs less.

Try Connect everything to reach the exact tie described above, then cut a single line and watch the list drop below the matrix again.

Common operations and their costs

Assuming an adjacency list, where V is nodes and E is edges:

Note how many of these are O(deg) rather than O(1) or O(n). Degree is the adjacency list's characteristic cost, and it's why a graph's shape — not just its size — determines how fast your code runs.

Graphs in the real world

Social networks

People are nodes, relationships are edges. Facebook built a dedicated distributed graph store, TAO, because a social graph's read pattern — fetch one node's neighbors, millions of times a second — is exactly what a general-purpose database is bad at. The representation, not the algorithm, was the bottleneck worth engineering.

Maps and routing

Intersections are nodes, roads are weighted edges. Road networks are extremely sparse — an intersection has maybe four roads, never four million — so they're stored as adjacency lists, usually in a compressed layout that trades editability for sequential reads.

Package managers and build systems

go mod graph prints a dependency graph, and every package manager keeps one. The DAG shape is the point: dependencies with no cycles admit a valid install order, and a cycle is a hard error you'll see reported as such.

Compilers

Compilers turn each function into a control-flow graph: basic blocks as nodes, possible jumps as edges. These graphs are small and often dense enough that a bitset-backed matrix is the right call — the opposite choice from a road network, for the same reasons in reverse.

Knowledge and recommendation graphs

Products, tags, users and their interactions form a graph where an edge means "related." Databases like Neo4j exist because expressing this in SQL means one join per hop, and the number of hops is exactly what you don't know ahead of time.

Databases

PostgreSQL keeps a wait-for graph of which transaction is blocked on which lock. It's a small directed graph maintained continuously, and its shape — specifically whether it contains a cycle — is what tells the database a deadlock has occurred.

When Graphs fall short

Graphs model almost anything, which is exactly why they're easy to reach for when something simpler would do.

Pointer chasing is cache-hostile. Walking an adjacency list means following map lookups and slice references scattered across memory, so nearly every step is a cache miss. Arrays win on locality by a wide margin. This is why serious graph processing abandons the friendly representation for compressed formats like CSR, which pack all the neighbor lists into two flat arrays and give up cheap mutation to get sequential reads back.

Matrices don't scale. O(V²) is fine at a thousand nodes and impossible at a million, and the edge count never enters it. Reach for a matrix only when you've established the graph is dense and bounded.

High-degree nodes skew everything. O(deg) is a comfortable bound until one node has a million edges. Real graphs follow power laws, so a handful of nodes dominate the cost of every operation, and the average degree tells you almost nothing about the worst case.

Mutation and concurrency don't mix. A Go map isn't safe for concurrent write, so a shared graph needs a mutex or a redesign. Worse, a read that holds a lock while it walks serializes everything — and one that doesn't can observe an edge list changing underneath it. Immutable snapshots are usually the answer.

Something simpler often fits. If your data has one root and no cycles, it's a tree, and tree code is shorter and faster. If you only ever ask "what is this node's parent," a hash table of parents beats a graph. Use a graph when you actually need arbitrary many-to-many relationships — not merely because your data has some relationships in it.

Summary

Graphs are the general case that every other structure in this series is a special case of:

• Nodes and edges — a graph models relationships, not sequence, and expresses many-to-many connections nothing else here can
• Direction and weight are storage decisions — an undirected edge is stored twice, and a weight is an extra field per edge or per cell
• Adjacency list for sparse, matrix for dense — O(V + E) against O(V²), and the crossover is exactly a complete graph
• Degree is the cost that matters — most adjacency-list operations are O(deg), so the graph's shape, not just its size, sets your performance
• Cycles are what separate a graph from a tree — no root, no order, and no guarantee that following edges terminates

The key insight is that graphs invert what a data structure is for. Arrays, linked lists, stacks, queues, and hash tables all organize values. A graph organizes connections, and the values become almost incidental — which is why picking a representation matters more here than in any structure so far. The same graph stored two ways can differ by orders of magnitude in memory and in the cost of the one question you ask most.

That's also why this article stops where it does. Choosing a representation is a data-structure decision, and it's the one you make first. What you then do with the graph — traversing it, finding shortest paths, detecting cycles, ordering a DAG — is a separate body of work, and it gets its own series.