Skip to content
Tutorials Center
My learning

Topics

Lesson 121 of 225 ยท Graphs

Graph Representations

Learn how to store a graph in Python: adjacency matrix, adjacency list, edge list and grids. Compare memory and speed, build graphs from input, and choose well.

A graph is an idea; to run an algorithm on it you must store it in memory. The way you store it decides how fast you can ask the questions every graph algorithm asks: "is there an edge between u and v?", "who are the neighbors of u?" and "give me all the edges". There are three classic representations, and a fourth trick for grids where the graph never needs to be stored at all.

This lesson builds each one in Python, counts what they cost, and gives a simple rule for choosing. If any term below is new (vertex, edge, degree, directed, weighted), start with Graphs.

The example graph

We will use this small undirected graph with five vertices numbered 0 to 4:

TEXT
   0 ----- 1
   |     / |
   |   /   |
   | /     |
   2 ----- 3       4 (alone)

edges: 0-1, 0-2, 1-2, 1-3, 2-3

Adjacency matrix

An adjacency matrix is a V by V table. Cell m[u][v] is 1 (or the edge weight) if there is an edge from u to v, and 0 (or infinity for weights) if not.

TEXT
     0  1  2  3  4
 0 [ 0  1  1  0  0 ]
 1 [ 1  0  1  1  0 ]
 2 [ 1  1  0  1  0 ]
 3 [ 0  1  1  0  0 ]
 4 [ 0  0  0  0  0 ]

For an undirected graph the matrix is symmetric: m[u][v] == m[v][u]. Checking an edge is a single lookup, O(1). Listing the neighbors of u means scanning a whole row, O(V). The matrix always uses O(Vยฒ) memory, even when there are almost no edges.

Python Building an adjacency matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Watch out: [[0] * n] * n looks like a shortcut but creates n references to the same row. Setting one cell then changes every row. Always build matrices with a comprehension: [[0] * n for _ in range(n)]. See Python You Need for DSA for the aliasing trap.

Adjacency list

An adjacency list stores, for each vertex, the list of its neighbors. In Python the natural fit is a list of lists (when vertices are 0..n-1) or a dictionary of lists (when vertices are names).

TEXT
0: [1, 2]
1: [0, 2, 3]
2: [0, 1, 3]
3: [1, 2]
4: []

Memory is O(V + E): one slot per vertex and one entry per edge direction (two entries per undirected edge). Listing neighbors of u costs O(deg(u)), exactly what BFS and DFS need. Checking whether a specific edge exists costs O(deg(u)) with a list, or O(1) if you store neighbors in a set instead.

For weighted graphs store pairs (neighbor, weight) or a dict of neighbor to weight.

Python Adjacency lists, undirected and weighted

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tip: defaultdict(list) creates the list the first time you touch a key, so you never write if u not in graph. Be careful, though: merely reading graph[x] also creates the key. Use graph.get(x, []) when you only want to look.

Edge list

An edge list is just a list of the edges, each as (u, v) or (u, v, weight). It is the smallest, simplest representation, O(E) memory, and it is what you usually receive as input.

It is awkward for neighbor queries (you must scan every edge), but ideal for algorithms that process edges as a whole: sorting edges by weight in Kruskal's algorithm (minimum spanning trees) or relaxing all edges repeatedly in Bellman-Ford.

Python Edge list and converting between representations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading a graph from input

Contest-style input usually gives n m (vertices and edges) and then m lines of u v. Here is the standard way to read it, with the input preset so you can press Run.

Python Reading a graph from input lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Comparing the three

Question Matrix Adjacency list Edge list
Memory O(Vยฒ) O(V + E) O(E)
Is there an edge u-v? O(1) O(deg u) (O(1) with sets) O(E)
Neighbors of u O(V) O(deg u) O(E)
Iterate all edges O(Vยฒ) O(V + E) O(E)
Add an edge O(1) O(1) O(1)
Remove an edge O(1) O(deg u) O(E)
Best for dense graphs, edge-lookup heavy code, Floyd-Warshall almost everything: BFS, DFS, Dijkstra sorting edges, Kruskal, Bellman-Ford

The usual advice: use an adjacency list unless you have a reason not to. Real graphs are sparse, and Vยฒ memory is hopeless for a million vertices (a trillion cells). A matrix is only worth it when V is small (a few thousand at most) and the graph is dense, or when you need constant-time edge checks.

Let's count the stored entries for a sparse graph, a path of 1,000 vertices:

Python Memory cost: matrix versus list on a sparse graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Grids are implicit graphs

Mazes, game boards and images are graphs where each cell is a vertex and neighbouring cells are joined by an edge. You almost never build an adjacency list for them. Instead write a neighbors function that computes the adjacent cells from the position, using four direction offsets (up, down, left, right) and a bounds check. The graph is implicit: it is defined by a rule, not stored.

TEXT
grid (# = wall, . = open)         neighbors of (1, 1) with 4 directions
. . #                             (0,1) up      open
. . .                             (2,1) down    open
# . .                             (1,0) left    open
                                  (1,2) right   open
Python A grid as an implicit graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For diagonal movement use eight offsets. For a hex grid or a game with special moves, change the offset list. The rest of the algorithm stays the same, which is why BFS on a grid is so reusable.

Choosing and common mistakes

  • Pick the representation by the operation you repeat the most. Traversals want neighbor lists. Floyd-Warshall wants a matrix. Kruskal wants an edge list.
  • Forgetting the reverse edge in an undirected graph. Adding adj[u].append(v) without adj[v].append(u) silently makes the graph directed.
  • Self-loops and duplicates. Decide whether parallel edges are allowed. Adding the same edge twice doubles it in a list but not in a matrix or set.
  • Using a list when you need fast edge lookup. v in adj[u] is O(deg u). If you ask it often on high-degree vertices, store neighbor sets.
  • Off-by-one vertex numbering. Input may be 1-indexed. Subtract 1 or allocate n + 1 slots, and be consistent.
  • Matrix for huge sparse graphs. A million vertices means 10ยนยฒ cells; the program will run out of memory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which representation uses O(V + E) memory and lists the neighbors of a vertex in O(degree)?

    An adjacency list has one entry per vertex and one per edge direction, and the neighbors are stored together.
  2. 2. What is the main weakness of the adjacency matrix?

    The table has V x V cells whatever the number of edges. Edge checks are O(1), which is its strength.
  3. 3. A graph has 10^6 vertices and 3 * 10^6 edges. Which representation is the sensible choice for BFS?

    A matrix would need 10^12 cells. The adjacency list stores about 7 * 10^6 items.
  4. 4. What is wrong with matrix = [[0] * n] * n?

    The outer multiplication repeats a reference to one inner list. Use a comprehension to create n separate rows.
  5. 5. Which task fits an edge list best?

    An edge list is already a flat collection of edges that can be sorted or looped over directly.

Summary

  • The three standard representations are the adjacency matrix (O(Vยฒ) memory, O(1) edge check), the adjacency list (O(V + E) memory, fast neighbors) and the edge list (O(E) memory, good for edge-centric algorithms).
  • In Python use list[list[int]] or defaultdict(list) for adjacency lists, (neighbor, weight) pairs for weights, and set neighbors for O(1) edge checks.
  • For an undirected graph, store every edge in both directions.
  • Grids are implicit graphs: compute neighbors from direction offsets and bounds checks instead of storing edges.
  • Default to the adjacency list; choose the matrix for small dense graphs and the edge list when you sort edges.
  • Build matrices with comprehensions to avoid shared rows.

Next: Breadth-First Search