12.1 Graph representations

Graphs are useful when a problem is mainly about connections. A road map asks which towns can be reached and by which route. A follower network asks which way information can travel. A task plan asks whether one job depends on another. Drawing each situation as a graph keeps the relationships that matter and lets us use the same search ideas across very different problems.

This is foundational discrete mathematics. You only need sets and simple tables to begin. MIT OpenCourseWare's Introduction to Algorithms lecture notes continue from representations into search.

A basic idea: the names for objects and connections

A graph is written $G=(V,E)$. The set $V$ contains vertices (also called nodes): the objects, such as towns or accounts. The set $E$ contains edges: the connections between them. An edge can be undirected, such as a two-way road $\{A,B\}$, or directed, such as a follow link $A\to B$ that does not imply $B\to A$. In a weighted graph, an edge carries a number such as road length or travel time; in an unweighted graph, edges have no such extra value and can be counted as individual moves. Decide what a vertex and an edge mean in the real problem before assigning these names.

In the directed diagram below, $V=\{A,B,C,D\}$ and $E=\{(A,B),(A,C),(B,D),(C,D)\}$. Each ordered pair names an arrow from its first vertex to its second. Vertex $D$ still belongs to the graph even though it has no outgoing arrow.

A quick tour of representations

A drawing is easy to inspect, but an algorithm needs a precise way to store the same graph. In a directed graph, $(A,B)$ and $(B,A)$ are different edges. The following layouts all preserve that direction when used correctly:

For vertex order $A,B,C,D$, the diagram's adjacency matrix has rows $A:(0,1,1,0)$, $B:(0,0,0,1)$, $C:(0,0,0,1)$, and $D:(0,0,0,0)$. In an undirected graph, the matrix is symmetric because every edge works both ways. In a weighted graph, a matrix entry can store a weight, but decide how to represent no edge separately; zero may itself be a valid weight.

With $n$ vertices, an adjacency matrix has $n^2$ entries even when there are few edges. An adjacency list stores the neighbours that actually exist. The choice changes storage and convenience, not the graph itself.

Application 1: a two-way road map

Towns $P,Q,R$ have two-way roads $P$–$Q$ of length $5$, $Q$–$R$ of length $2$, and $P$–$R$ of length $9$. Write an adjacency list.

1. Use both directions. $P:\ (Q,5),(R,9)$; $Q:\ (P,5),(R,2)$; $R:\ (P,9),(Q,2)$.
2. Check symmetry. The $P$–$Q$ road appears under both $P$ and $Q$ with the same length.
3. Keep the meaning. These weights are distances, not probabilities. A later path algorithm could compare the direct $P$–$R$ length $9$ with the route through $Q$ of length $7$.

Application 2: one-way follows

Accounts $A,B,C$ have follows $A\to B$, $A\to C$, and $C\to A$. Who does $B$ follow, and which follows point back to $A$?

1. List outgoing neighbours. $A:[B,C]$, $B:[]$, $C:[A]$.
2. Answer by direction. $B$ follows nobody in this graph. Only $C$ has an edge pointing to $A$.
3. Avoid an undirected reading. $A\to B$ does not add $B\to A$.

The same three account names would give different reachability answers if the arrows were removed.