Graph Representations

• Graph Theory Fundamentals: vertices, edges, degree, directed and undirected graphs.
• Linked Lists: adjacency lists are linked lists.
• Arrays: Address Calculation and Special Matrices: two-dimensional arrays.

Terminology needed here

• In an undirected graph, edge $\{u, v\}$ makes $u$ and $v$ adjacent; the degree $\deg(u)$ is the number of incident edges.
• In a directed graph, edge $(u, v)$ goes from $u$ to $v$; $u$ has out-degree and in-degree.
• Handshake lemma: $\sum_{u} \deg(u) = 2m$ (undirected); $\sum_u \text{out}(u) = \sum_u \text{in}(u) = m$ (directed).
• A simple undirected graph has at most $\binom{n}{2} = n(n-1)/2$ edges; a simple directed graph at most $n(n-1)$.
• Dense: $m$ close to $n^2$. Sparse: $m$ much smaller than $n^2$, for example $m = O(n)$.

Running example

Adjacency matrix

• Undirected graph: $A$ is symmetric; only the upper triangle needs storing ($n(n-1)/2$ entries without the diagonal; see triangular storage).
• Simple graph: zero diagonal.
• Row sum of row $u$ = degree (undirected) or out-degree (directed); column sum = in-degree.
• The transpose $A^{\mathsf T}$ represents the graph with every edge reversed.
• Powers: the entry $(A^k)[u][v]$ is the number of walks of length exactly $k$ from $u$ to $v$. In the example $A^2[0][3] = 1$ (the walk 0, 1, 3), and the diagonal of $A^2$ is the degree sequence. The number of triangles in a simple undirected graph is $\operatorname{trace}(A^3)/6$; here it is 1 (vertices 0, 1, 2).

Adjacency list

struct edge { int to; struct edge *next; };        /* add an int weight field if weighted */
struct edge *adj[V];                                /* adj[u]: head of u's list */

void add(int u, int v) {                            /* insert at head: O(1) */
    struct edge *e = malloc(sizeof *e);             /* allocation check omitted for brevity */
    e->to = v; e->next = adj[u]; adj[u] = e;
}
/* undirected edge {u, v}: add(u, v); add(v, u); */

0: 2 1
1: 3 2 0
2: 1 0
3: 4 1
4: 3

• Total list entries: $2m$ for undirected graphs, $m$ for directed graphs.
• Length of the list of $u$ = degree (out-degree for directed).
• Finding the in-degree of $u$ in a directed graph needs a scan of all lists: $O(n + m)$.
• The reversed graph $G^{\mathsf T}$ is built from the lists in $O(n + m)$.

Edge list and incidence matrix

• Edge list: an array of the $m$ pairs $(u, v)$ (with weights). Space $\Theta(m)$. Natural for Kruskal's algorithm, which sorts edges by weight (Minimum Spanning Trees).
• Incidence matrix: $n \times m$, entry 1 if the vertex is an endpoint of the edge. Each column of an undirected incidence matrix has exactly two 1s; row sums are the degrees. With $B$ the incidence matrix, $BB^{\mathsf T} = D + A$, where $D$ is the diagonal matrix of degrees. Rarely used for algorithms because it costs $\Theta(nm)$ space.

• Sparse graphs (most real graphs, trees, planar graphs) favour lists: $\Theta(n + m)$ space and traversal.
• Dense graphs, or algorithms that need many $O(1)$ edge tests (for example Floyd-Warshall all-pairs shortest paths), favour the matrix.
• BFS and DFS cost $\Theta(n + m)$ with lists and $\Theta(n^2)$ with a matrix, because scanning a matrix row costs $n$ no matter how few neighbours there are.

• Matrix: $\Theta(n^2)$ space regardless of $m$; $O(1)$ edge test.
• Lists: $\Theta(n + m)$ space; neighbour iteration proportional to degree.
• An undirected graph's matrix is symmetric; each undirected edge appears twice in the lists.
• The order of entries in each adjacency list decides tie-breaking in BFS and DFS.
• $A^k$ counts walks of length $k$; $\operatorname{trace}(A^3)/6$ counts triangles in a simple undirected graph.

• Space or time with a given representation: BFS or DFS is $\Theta(n + m)$ with lists, $\Theta(n^2)$ with a matrix.
• Degrees and edge counts from a matrix or from lists, using the handshake lemma.
• Traversal orders that depend on adjacency list order.
• Matrix facts: symmetry, row and column sums, transpose, powers counting walks.
• Dense versus sparse choice for a stated algorithm.

• Graph Theory Fundamentals: prerequisite.
• Linked Lists: prerequisite.
• Breadth-First Search: dependent. Uses a queue.
• Depth-First Search and Edge Classification: dependent. Uses a stack or recursion.
• Minimum Spanning Trees: Kruskal and Prim: dependent.