Graph Representation

Adjacency matrices

A simple directed graph with $n$ vertices and no loops or parallel edges has at most $n(n-1)$ edges; a simple undirected graph has at most $n(n-1)/2$. An adjacency matrix G[N][N] expresses vertex relationships directly.

For an unweighted graph, an entry is 1 when the edge exists and 0 otherwise.

The diagonal is 0 for the simple graphs discussed here because self-loops are excluded. An undirected graph's adjacency matrix is symmetric: if A connects to B, B connects to A.

A directed graph's matrix need not be symmetric. A may reach B directly without a reverse edge.

For a weighted network, store the edge's weight in the corresponding entry.

For distinct vertices with no edge, use $\infty$ rather than 0. When initializing shortest-path distances, set the diagonal to 0.

Advantages:

1. Simple and intuitive.

2. Fast lookup of whether two vertices are adjacent.

3. Convenient degree calculations. In a directed graph, outgoing edges determine outdegree and incoming edges determine indegree.

Disadvantages:

1. Sparse graphs waste space on many unused entries. Dense graphs, especially complete ones, use the matrix more effectively.

2. Counting edges in a sparse graph requires scanning many entries.

Adjacency lists

Adjacency lists address the matrix's space cost. Each vertex heads a linked list of the neighboring vertices it can directly reach. For sparse graphs, this uses much less storage than a matrix.

Scanning a vertex's list finds its outgoing neighbors. The reverse question—who can reach this vertex—is less convenient.

A reverse adjacency list stores the vertices that directly reach each vertex instead.

Maintaining both lists separately is cumbersome.

An orthogonal, or cross-linked, list combines the outgoing and incoming chains.