Graph Representations
Adjacency list · adjacency matrix · incidence matrixTo work with a graph in a program you have to store it. An adjacency list keeps the neighbours of every vertex, an adjacency matrix keeps a table of which vertices are joined, and an incidence matrix keeps a column for every edge. Build each one edge by edge, then ask it questions and see how much work each answer takes — for undirected and for directed graphs.
- Adjacency lista list of neighbours per vertex: V + E
- Adjacency matrixa V × V table of 0 and 1: V²
- Incidence matrixa V × E table, a column per edge
- Current
- Looking at
- Done
- Edge / neighbour
Ready
Edges are written A-B (letters A–H, up to 12 edges) · Keyboard: ← → step · Space play / pause · R reset
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Three ways to store a graph
An ADJACENCY LIST keeps, for every vertex, the list of its neighbours — small when there are few edges. An ADJACENCY MATRIX is a V × V table with a 1 where an edge exists — one look answers "is there an edge u → v?", but it always uses V² cells. An INCIDENCE MATRIX is a V × E table with one COLUMN per edge — every edge points to its two ends. Undirected edges put 1 at both ends; directed edges put −1 where the edge leaves and +1 where it arrives.
// Adjacency list: adj[u] = the neighbours of u
int adj[V][V]; int deg[V]; // adj[u][0 .. deg[u]-1]
// Adjacency matrix: m[u][v] = 1 if there is an edge u -> v
int m[V][V];
// Incidence matrix: one column per edge
int inc[V][E]; // undirected: 1 at both ends
// directed: -1 at the tail (leaves), +1 at the head (arrives)
// An undirected edge A - B is stored twice in the list and the matrix
// (A -> B and B -> A) but only once in the incidence matrix.
Adjacency list
- One list per vertex, holding its neighbours.
- Adding an edge appends to a list (twice if undirected).
- Memory: V + E entries (V + 2E if undirected).
- The neighbours of u are just the list of u.
Adjacency matrix
- A V × V table, every cell starts at 0.
- Edge u → v sets m[u][v] = 1 (undirected: m[v][u] too).
- Is there an edge? One look at one cell: O(1).
- Memory: always V², however few edges.
Incidence matrix
- One ROW per vertex, one COLUMN per edge.
- Undirected: put 1 in the rows of the two ends.
- Directed: −1 where the edge leaves, +1 where it arrives.
- Memory: V × E cells. Finding an edge means scanning columns.
Directed vs undirected
- Undirected adjacency matrix is symmetric: m[u][v] = m[v][u].
- Directed: row u shows where u points, column v shows who points at v.
- Every incidence column of an undirected graph has exactly two 1s.
- Every directed column has one −1 and one +1.
Weights
- List: store (neighbour, weight) pairs.
- Matrix: store the weight instead of 1 (∞ or 0 for "no edge").
- Incidence: store the weight in the end cells.
- Floyd–Warshall starts from exactly such a weight matrix.
Which one?
- Few edges (sparse), most real graphs: adjacency list.
- Many edges or constant edge checks: adjacency matrix.
- Algorithms that work edge by edge (cuts, flows): incidence matrix.
- Search and shortest paths on big graphs: adjacency list.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
V = vertices, E = edges, degree = the neighbours of one vertex. The list is the smallest for sparse graphs; the matrix answers edge questions instantly.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Add an edge (list or matrix) | O(1) |
O(1) |
O(1) |
Instant |
| Add an edge (incidence matrix) | O(V) |
O(V) |
O(V) |
Grows with n |
| Is there an edge u–v? (list) | O(1) |
O(degree) |
O(V) |
Grows with n |
| Is there an edge u–v? (matrix) | O(1) |
O(1) |
O(1) |
Instant |
| Is there an edge u–v? (incidence) | O(1) |
O(E) |
O(E) |
Grows with n |
| Neighbours of u (list) | O(1) |
O(degree) |
O(V) |
Grows with n |
| Neighbours of u (matrix) | O(V) |
O(V) |
O(V) |
Grows with n |
| Neighbours of u (incidence) | O(E) |
O(E) |
O(E) |
Grows with n |
The three representations
| Adjacency list | Adjacency matrix | Incidence matrix | |
|---|---|---|---|
| Shape | A list for every vertex | V × V table | V × E table |
| Memory | O(V + E) | O(V²) | O(V × E) |
| Is u joined to v? | Scan u's list: O(degree) | One cell: O(1) | Scan the columns: O(E) |
| All neighbours of u | O(degree) — the list | O(V) — a whole row | O(E) — every column |
| Add an edge | O(1) | O(1) | O(V) — a new column |
| Undirected edge stored | Twice (u in v, v in u) | Twice (m[u][v] and m[v][u]) | Once (one column, two 1s) |
| Best for | Sparse graphs — most real graphs | Dense graphs, quick edge checks | Edge-centred algorithms |
Directed incidence matrix: reading a column
| Entry in the column of edge u → v | Meaning |
|---|---|
| −1 in the row of u | The edge LEAVES u (u is the tail) |
| +1 in the row of v | The edge ARRIVES at v (v is the head) |
| 0 everywhere else | The edge does not touch that vertex |
Some books use the opposite signs — what matters is that the two ends get opposite signs, so the column adds up to 0.
Check your understanding
Answer each question — you will see the explanation straight away.
An undirected graph has 5 edges. How many entries does its adjacency list have in total?
Each undirected edge u–v is stored twice: v in the list of u and u in the list of v.
A graph has 1,000 vertices and only 2,000 edges. Which representation uses the least memory?
The list needs about V + 2E = 5,000 entries. The matrix needs 1,000,000 cells and the incidence matrix 2,000,000.
Which representation answers "is there an edge from u to v?" in O(1)?
In the matrix you look at ONE cell, m[u][v]. The list must scan u's neighbours and the incidence matrix must scan the edge columns.
The adjacency matrix of an undirected graph is always…
An undirected edge u–v sets BOTH m[u][v] and m[v][u], so the table mirrors itself across the diagonal.
In the incidence matrix of an undirected graph, how many non-zero entries does each column have?
A column belongs to one edge, and an edge has exactly two ends: two 1s, everything else 0.
In a directed incidence matrix, the column of the arrow A → B has…
With the usual convention −1 marks the vertex the edge leaves (A) and +1 the vertex it arrives at (B).
What is the size of the incidence matrix of a graph with 6 vertices and 9 edges?
One row for every vertex and one column for every edge: V × E = 6 × 9 = 54 cells.
To find ALL the neighbours of a vertex u in an adjacency matrix, you must…
The 1s in row u are the neighbours, but you only know where they are by looking at all V cells of the row.
Graphs quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.