--- title: "Graphs and How to Store Them" description: "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 question" canonical: https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu source: https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18 Page: https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu ## Ready when they can - 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 ## Lesson: Storing maps as matrices or lists 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. **Example.** 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. *(drawing: These matrix rows store P to Q and Q to R. Row names identify sources; column names identify destinations.)* 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. *(drawing: This directed graph uses a one-bit-per-cell matrix or 32-bit neighbour IDs. The list total excludes overhead.)* 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. *(drawing: Each entry stores a destination and distance. These roads are directed; no reverse roads are listed.)* 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. **Recap.** 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.* ## Practice 17 questions on this page, each with its working shown. ## Needs first - [Trees and Binary Search Trees](https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b) ## Opens up - [Graphs, Degrees and the Handshake Lemma](https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO) - [Wide-Column and Graph Stores](https://lightmysky.com/learn/computing/wide-column-and-graph-stores-mt_4a4yDq83fy) - [Deadlock and the Four Conditions](https://lightmysky.com/learn/computing/deadlock-and-the-four-conditions-mt_CsMOA4sBb1) - [Version Control as a Graph of Commits](https://lightmysky.com/learn/computing/version-control-as-a-graph-of-commits-mt_oKsDRKirMy) - [Breadth-First and Depth-First Search](https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy) - [Union-Find and Minimum Spanning Trees](https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr)