Core12 min read

Graphs and their representations

Vertices and edges model relationships; adjacency lists and matrices are two ways to store the same graph with different costs.

Trees are graphs with rules. Remove the rules — allow any node to connect to any other, allow cycles, allow direction on the edges — and you get the most general relational structure in computer science. Maps, social networks, dependency graphs and the web itself are all graphs, and almost every AI pipeline ends up walking one.

Vertices are things, edges are relationships

A graph is a set of vertices plus a set of edges that say which pairs are connected. Everything else — directions, weights, labels — is extra data on top. Once you can name the things and the relationships, you can choose a representation and an algorithm.

Add edges below and flip between an adjacency list and an adjacency matrix to see the same graph stored two ways.

Add edges and switch how the graph is stored

directed

→|V|=5 · |E|=5

A: [B, C]

B: [A, D]

C: [A, D]

D: [B, C, E]

E: [D]

list memory ≈ 5 + 10 entriesmatrix memory = 25 cells

Adjacency lists win on sparse graphs (most real graphs) because memory scales with the number of edges. Matrices win when the graph is dense or when the question is "is there an edge?" — that check is one array lookup. To be undirected, an edge is stored in both directions.

Vocabulary

Directed edges have a direction (u → v is not v → u); undirected edges are mutual.
Weighted edges carry a number such as a distance or cost.
The degree of a vertex is how many edges touch it; in a directed graph, in-degree and out-degree are counted separately.
A path is a sequence of edges; a cycle returns to where it started.
A graph is connected if every vertex is reachable from every other.

Two representations

An adjacency list stores, for each vertex, the list of its neighbours. It uses $O(V + E)$ space and enumerates neighbours in time proportional to their number — ideal for sparse graphs, which is almost all real ones.

An adjacency matrix is a $V \times V$ grid of 0s and 1s. It uses $O(V^2)$ space but answers "is there an edge between u and v?" in $O(1)$ and is convenient when the graph is dense or the algorithm is matrix-flavoured.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "F"],
    "D": ["E"],
    "E": [],
    "F": [],
}

This is an adjacency list built from a dict, with a list per vertex. To make it undirected, add each edge in both directions; to make it weighted, store (neighbour, weight) pairs instead of bare neighbours.

Sparse graphs punish matrices

A matrix for a graph with a million vertices needs a trillion cells even if it has only a few million edges. Always ask how dense the graph is before picking a representation — the wrong choice can be the difference between fitting in memory and not.

Graphs also generalise everything from this chapter: a linked list is a path graph, a tree is a connected acyclic graph, and a grid is a graph whose neighbours are the cells above, below, left and right.

Illustrative vs real

The panel uses five vertices and a handful of edges so the list and matrix fit side by side. Real graphs have millions of vertices, arrive as edge streams, and are often stored in compressed formats. The space formula — $O(V+E)$ for a list versus $O(V^2)$ for a matrix — is the whole point of the comparison.

Check yourself

Eduspheria wiki · Programming & Data Structures, Data structures

0 / 5 answered

1What is the space complexity of an adjacency list for a graph with V vertices and E edges?
Multiple choice
2In an undirected graph, the edge A–B is stored in both A's and B's adjacency lists.
True / false
3What is the term for the number of edges touching a vertex?
Short answer
4Which representation answers "is u adjacent to v?" in O(1)?
Multiple choice
5A complete undirected graph has 5 vertices. How many edges does it have?
Numeric answer

From the assignment paper

Modeled on NITJ AI-507, Assignment/Quiz

0 / 6 answered

1In an undirected graph, what is the number of edges touching a vertex called?
Multiple choice
2How is a graph typically represented in Python?
Multiple choice
3A graph that contains no cycles is described as what?
Multiple choice
4What defines a strongly connected directed graph?
Multiple choice
5Which statement about a tree is false?
Multiple choice
6A tree has 12 vertices. How many edges does it have?
edges
Numeric answer

Where next: asymptotic analysis — the language for saying how these costs grow as the input does.

Vocabulary #

Two representations #

Vocabulary

Two representations