Graphs and How to Store Them
Nodes joined by edges, with the edges possibly directed and possibly carrying a weight. The same graph can be held as an adjacency matrix or as an adjacency list, and the choice decides which questions are cheap to ask.
What a learner can do afterwards
- Write the same small graph as an adjacency matrix and as an adjacency list
- Compare matrix and list storage for sparse and dense graphs, stating the memory encoding and lookup needs
- Model a real situation, such as a route map, as nodes, edges and weights
1 · Read
Trees use nodes and links. An undirected tree is connected and has no cycles; choosing a root makes it a rooted tree. A graph also has nodes and edges, but may have cycles or separate parts. Places on a route map can be nodes, with roads as edges. A directed edge goes from one node to another. A weight records a quantity such as distance.
For an unweighted graph, an adjacency matrix has one row and column per node. The row gives the source and the column gives the destination: 1 means an edge exists, and 0 means none. An adjacency list names each node's direct neighbours. With directed edges P to Q and Q to R, row P across P, Q, R is 0, 1, 0, and P's list entry is P: Q.
Keep a list entry for every node, even with no neighbours. For directed graphs, each listed neighbour is one edge; add entries to count all edges. In a matrix, count 1s in a row for edges leaving its node, or in a column for edges entering it. An undirected edge appears at both endpoints and in both matrix directions. Without self-loops, halve the total neighbour entries to count undirected edges.
A full matrix for n nodes has n rows and n columns: n times n cells, even if edges are missing. A packed unweighted matrix can use one bit per cell. A list using 32-bit neighbour IDs uses 32 times the number of recorded neighbours in bits, before overhead. Compare these sizes to choose a store. Dense graphs can favour a packed matrix, but the answer depends on the encoding.
A sparse graph has far fewer edges than possible. A list stores one entry per node and only actual neighbours, often saving memory compared with a full matrix. A matrix can check an edge by reading one cell, without scanning a row. With neighbours in an unsorted list, you may need to scan that node's entries. Choose storage for both memory use and the queries you need.
To model roads, use places as nodes and roads as edges. A one-way road needs a directed edge. Road lengths are weights. For example, roads from Pine to Lake at 4 km and Lake to Mill at 7 km give weighted entries Pine: (Lake, 4) and Lake: (Mill, 7). A two-way road appears in the lists of both endpoints.
Changing a road's distance changes its weight, not its endpoints. Weighted lists store neighbours with weights. A weighted matrix stores a weight at each road's cell. Choose a distinct missing-edge marker, such as null. A weight of 0 can be valid, so it must not also mean no edge.
Matrices store every node pair; lists store neighbours. Keep directions and weights, and compare memory use with the queries you need.
Graph-storage lesson, questions and flashcards written for this dataset.
Additional graph-storage questions, reading and flashcards written for this dataset.
More to read
Keeping connections when storage changes
Changing a graph's storage should not change its nodes or edges. A node with no neighbours still needs a record. A one-way connection must not acquire a reverse connection during conversion.
Read a directed matrix by matching row names to sources and column names to destinations. To convert a row to a list, retain the destinations marked as connected. To rebuild that row, place a connection mark at each listed destination and a missing-edge mark elsewhere.
For an undirected edge, both endpoints list each other. Its matrix entries also appear in both directions. Without self-loops, counting every neighbour entry therefore counts each edge twice.
Representation affects work as well as memory. A matrix lets you inspect one known node pair directly. An unsorted neighbour list may require a search for that destination. Lists avoid allocating missing-edge cells, while a packed unweighted matrix can be small when many pairs are connected. Compare the actual encodings and the questions your program asks.
Numbers on edges need a separate absence convention. If zero is a permitted weight, a zero-weight edge must remain distinguishable from a missing edge. A marker such as null makes that distinction explicit.
2 · Watch
Take it off screen
Where it sits
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.