--- 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-09-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 - Say which storage suits a sparse graph and which suits a dense one, with the reason - Model a real situation, such as a route map, as nodes, edges and weights ## Lesson: Storing maps as matrices or lists A graph is nodes joined by edges, and the edges can be directed and can carry a weight like a distance. You store the same graph two ways: an adjacency matrix, a grid with one row and column per node marking links, or an adjacency list, where each node just names its neighbours. **Example.** Take nodes A, B, C, D with edges A to B, A to C, B to D, C to D. Row A of the matrix reads 0, 1, 1, 0 across A, B, C, D. The list entry is shorter: A names B, C. Counting the names in a full list, like A: B, C with B: C and C: none, gives 3 directed edges. You pick by density. A sparse graph has far fewer edges than possible pairs, so a list wins by storing only real edges. A dense graph joins most pairs, so the matrix grid of marks is more compact. A matrix for n nodes always holds n rows by n columns, so 6 nodes need 36 cells. **Tip.** You model a route map by turning places into nodes and roads into edges. Ashcombe, Bridgeton and Cliffwood become nodes, and the 5 km and 8 km road lengths become edge weights on the roads joining them. **Recap.** Matrices grid every pair while lists name neighbours, and density decides the cheaper store. ## 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)