vizlearn
Home / Algorithms

Graph Representations

Algorithms & Data StructuresBy Updated

The same graph, stored two ways. One answers “are these connected?” instantly but wastes memory; the other is compact but must scan. Toggle between them and watch the costs swap.

Controls

vertices6
density30%

Same Graph, Two Storages

step 0

Insight

A graph is vertices plus edges. How you store the edges decides which operations are cheap.

vertices V6
edges E0
matrix memory0
list memory0

Complexity

Matrix edge check O(1)
List edge check O(degree)
Matrix space O(V²)

Overview

A graph is a set of vertices connected by edges. Every graph algorithm on this site — BFS, DFS, Dijkstra, A* — assumes some way of storing those edges. And that choice quietly decides their performance.

What this is

The three standard representations are the adjacency matrix, the adjacency list. And the edge list. Each trades space for speed on different operations.

Adjacency Matrix

A V×V grid where M[i][j] = 1 means an edge exists from i to j.

  • Edge lookup is O(1) — one array access. Unbeatable.
  • Space is O(V²) regardless of edge count. A graph with 10,000 vertices needs 100 million entries even if it has ten edges.
  • Listing a vertex's neighbours costs O(V) — you must scan an entire row, mostly zeros.

For an undirected graph the matrix is symmetric, so half of it is redundant.

Adjacency List

An array of lists: each vertex stores only the neighbours it actually has.

  • Space is O(V + E) — proportional to real edges, not possible ones.
  • Iterating neighbours is O(degree) — exactly what BFS and DFS do at every step. This is why they use lists.
  • Edge lookup is O(degree) — you scan the list rather than jumping to it.

The same graph in both forms

Take four vertices A, B, C, D and edges A–B, A–C, C–D. The adjacency list stores A: [B, C], B: [A], C: [A, D], D: [C]. An undirected adjacency matrix records the same links in a 4×4 grid, with mirrored entries for each edge. The list stores only the six neighbor references; the matrix reserves all 16 cells.

The Rule of Thumb

Slide density and watch the two memory figures cross over.

  • Sparse graphs (E &lll; V²) — use an adjacency list. Road networks, social graphs and web links are all sparse: most pairs are not connected.
  • Dense graphs (E approaching V²) — a matrix becomes competitive on memory and wins outright on lookup speed.

Real-world graphs are by far sparse, which is why the adjacency list is the default in practice.

It Changes Algorithm Cost

This is not just a storage detail. BFS and DFS are O(V + E) with an adjacency list but O(V²) with a matrix, because each vertex must scan a whole row. On a sparse graph with a million vertices that is the difference between seconds and hours.

Similarly, Dijkstra is O(V²) with a matrix and simple scanning, but O((V+E) log V) with an adjacency list and a binary heap.

A Third Option: Edge List

Simply a list of (u, v, weight) triples. Terrible for asking "who are u's neighbours?" but ideal when an algorithm processes every edge in sorted order — which is exactly what Kruskal's MST algorithm does.

Experiments to try with Graph Representations

  1. Start at 30% density. The matrix is mostly zeros — every one of them still occupies memory.
  2. Switch to the adjacency list. The same graph, stored in a fraction of the space, with only real edges recorded.

Sources and next steps

Run it in Python

The same six-node graph stored three ways, with the cost of each question measured against each store. Nothing here is an opinion — the memory figures come from sys.getsizeof and the operation counts are counted.

representations.pyPython 3
Output
How the code works
  1. adj_list[u].append(v); adj_list[v].append(u)Both directions, because the graph is undirected. Drop the second line and you have a directed graph — that one line is the entire difference in code.
  2. matrix = [[0] * len(nodes) for _ in nodes]V×V cells allocated up front, whether or not there are edges to put in them. For a social network of a million users that is 10¹² cells to store a few hundred million edges.
  3. matrix[index["A"]][index["D"]]Constant time, and unbeatable. If the question your program asks most often is “are these two connected?”, this is the representation.
  4. adj_list["D"]Also constant time, and it returns the neighbours themselves. Traversal algorithms — BFS, DFS, Dijkstra — ask this question and never the other one, which is why they all assume an adjacency list.
  5. V*V versus 2*EThe whole trade-off in two numbers. Matrices cost O(V²) always; lists cost O(V + E), which is smaller exactly when the graph is sparse — and real graphs almost always are.
Change one thing
  • Add the edges to make the graph complete (every node to every other). The matrix cost does not move; the list cost climbs to meet it.
  • Delete the adj_list[v].append(u) line and print the result. You now have a directed graph, and adj_list["F"] is empty.
  • Store weights instead of 1s in both structures. The matrix takes it without a change of shape; the list has to hold pairs.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set density to its maximum (100). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. For a sparse graph, an adjacency matrix wastes space because it stores:
  2. "Is there an edge between A and D?" is answered fastest by:
  3. BFS, DFS and Dijkstra all assume an adjacency list because they ask:





 Cheat sheet
Graph Representations
Store a graph as an adjacency matrix, adjacency list or edge list and see how the choice changes the cost of every algorithm on it.
ALGORITHMS · vizlearn.in/dsa/graph_representations.html
More in Algorithms
AlgorithmsBreadth First SearchAlgorithmsDepth First SearchAlgorithmsCycle DetectionAlgorithmsTopological Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact