Graph Representations

Road maps, social networks, task dependencies, links between web pages: all graphs. Before any graph algorithm runs you must decide how the graph lives in memory, and that choice can change the running time a thousandfold.

beginner⏱ 8 min read

←Builds on

5Trees: Concepts, Properties, TraversalsA tree is a connected graph without cycles; graphs simply drop that restriction.1Arrays & Dynamic ArraysAn adjacency list is an array of dynamic arrays, one per vertex.

Leads to→

6Breadth-First Search (BFS)BFS walks the adjacency list of each vertex it takes out of the queue.8Bellman–Ford & Negative EdgesIt simply loops over the edge list V − 1 times.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Vertices, edges and three flavours

A graph G = (V, E) is a set of vertices and a set of edges, each edge joining two vertices. V also denotes the number of vertices and E the number of edges.

Undirected: an edge u–v can be walked both ways (a friendship, a road open both ways).
Directed: an edge u→v has a direction (following someone, “course A is required before B”).
Weighted: every edge carries a number: a length, a price, a time.

Two more words you will need. The degree of a vertex is the number of edges touching it. A graph is sparse when E is close to V and dense when E approaches V². Most real graphs (roads, the web, friendships) are sparse. A tree is the special case you already know: connected, undirected, no cycles, E = V − 1.

02Adjacency matrix

The most direct storage is a V×V table: M[u][v] = 1 if there is an edge u–v and 0 otherwise. For a weighted graph store the weight, and something like ∞ for “no edge”. In an undirected graph every edge fills two cells, M[u][v] and M[v][u], so the matrix is symmetric.

Strength: “is there an edge between 2 and 5?” is one array lookup, O(1), and the code is trivial. Floyd–Warshall and many dynamic programming tricks on graphs are naturally written on a matrix.

Weakness: it always takes V² memory, and listing the neighbours of u means scanning its whole row, O(V), even when u has two neighbours. For V = 100 000 the matrix has 10¹⁰ cells: impossible. Rule of thumb: a matrix is fine up to a few thousand vertices, or when the graph is dense anyway.

03Adjacency list and edge list

An adjacency list keeps, for every vertex, the list of its neighbours: vector<vector<int>> g(n); and for each edge u–v, g[u].push_back(v); g[v].push_back(u);. Memory is V + 2E for an undirected graph (V + E if directed), and visiting the neighbours of u costs exactly deg(u), no wasted zeros. That is what BFS, DFS and Dijkstra do all day, so they all use lists. For weights, store pairs: vector<vector<pair<int,int>>>.

An edge list is even simpler: just the E pairs (u, v), perhaps with weights. Most problems give you their input in exactly this form, and it is the right shape when an algorithm processes edges rather than vertices: Kruskal sorts the edge list by weight, Bellman–Ford loops over it again and again.

Usually you read the edge list from the input and immediately build adjacency lists from it.

04Which one to choose

Ask what your algorithm does most often:

it walks from a vertex to its neighbours (BFS, DFS, Dijkstra, Prim, topological sort): adjacency list, O(V + E) memory and time;
it asks “is u–v an edge?” a lot, or V is small and the graph dense (Floyd–Warshall, bitmask DP over vertices): matrix;
it processes edges one by one, or in sorted order (Kruskal, Bellman–Ford): edge list.

Two pitfalls. Indexing: problems usually number vertices from 1, so allocate n + 1 lists or subtract 1 when reading. And in an undirected graph add both directions; forgetting the second push_back is the most common graph bug there is.

Some graphs need no storage at all. In a grid maze the neighbours of cell (r, c) are computed on the fly: (r ± 1, c) and (r, c ± 1).

Cost at a glance

Matrix: memoryO(V²)

Matrix: is u–v an edge?O(1)

Adjacency list: memoryO(V + E)

Adjacency list: neighbours of uO(deg u)

Remember

An adjacency matrix answers “is u–v an edge?” in O(1) but always costs V² memory.
Adjacency lists cost O(V + E) and hand each vertex its neighbours directly, which is why BFS, DFS and Dijkstra use them.
The edge list is the usual input format and the right shape for algorithms that scan edges, like Kruskal and Bellman–Ford.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Each revealed edge writes two matrix cells and two list entries. At the end compare the 25 matrix cells with the 12 list entries.

Interactive visualizerfocus here, then space ← →

Graph

Adjacency matrix

	1	2	3	4	5
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	0
4	0	0	0	0	0
5	0	0	0	0	0

Adjacency list

Edge list

∅

A graph is vertices connected by edges. There are two standard ways to store it. Watch both fill as we reveal each edge.

Pseudocode

 1 a graph = vertices V + edges E 2 adjacency matrix: M[u][v] = 1 if edge u–v      (V×V) 3 adjacency list: list[u] = neighbours of u      (V + E) 4 edge exists? matrix O(1)  ·  list O(degree) 5 iterate neighbours: list wins → BFS/DFS/Dijkstra use lists

1 / 1

Check

Three questions. Pick an answer to see why.

A road network has 200 000 intersections and 500 000 roads, and you will run BFS on it. Which representation?

An undirected graph has 5 vertices and 6 edges. How many entries do its adjacency lists hold in total?

Kruskal’s algorithm processes edges from cheapest to most expensive. What is its natural input?

Practice

Real problems to lock it in, easiest first.

LeetCodeFind Center of Star Graph beginner↗LeetCodeFind the Town Judge beginner↗LeetCodeFind if Path Exists in Graph beginner↗LeetCodeNumber of Provinces intermediate↗