Graph Representation

Graph representation turns vertices and edges into data a program can store and query. An adjacency list keeps one neighbor row per vertex and uses O(V + E) space. An adjacency matrix reserves a V by V grid, spends O(V²) space, and answers has_edge(u, v) with one indexed lookup.

Think of the list as an address book: open vertex u and read only the neighbors it actually has. The matrix is a seating chart with a box for every possible pair, including the pairs that never meet. The empty boxes cost space; the fixed coordinates buy speed.

Graph representation trades space for lookup speed

The lesson uses a simple undirected graph. "Simple" means no parallel edges and no self-loops. "Undirected" means edge u-v has no preferred direction, so both representations must store it symmetrically.

In an adjacency list, edge u-v performs two appends: put v in adj[u], then put u in adj[v]. Each undirected edge therefore contributes two neighbor entries. Across the whole graph, the rows hold exactly 2E entries, plus one row head for each of the V vertices.

In an adjacency matrix, the same edge sets two cells: matrix[u][v] = 1 and matrix[v][u] = 1. The two ones mirror each other across the main diagonal. A zero means no edge. Because this lesson excludes self-loops, the diagonal stays zero.

That symmetry is the invariant. If the list stores both directions but the matrix writes only one cell, the structures describe different graphs. If the list appends only one direction, it has quietly become a directed graph while the picture still claims otherwise.

The two structures make different operations cheap. A list can report degree(u) from the length of row adj[u]. To test whether u-v exists, however, it scans that row until it finds v or reaches the end. A matrix does the reverse trade: degree requires summing an entire row, but edge membership is the single cell matrix[u][v].

Graph representation step by step

The default graph has vertices 0 through 5 and five edges, processed in this order:

0-1, 0-2, 1-3, 2-3, 3-4

Vertex 5 is isolated. That is deliberate; a graph representation should not need special pleading to store a vertex with degree zero.

1. Allocate six empty list rows and a 6 by 6 matrix of zeros.
2. Encode edge 0-1. Append 1 to adj[0], append 0 to adj[1], then set matrix cells [0][1] and [1][0] to 1.
3. Encode edge 0-2 the same way. Rows adj[0] and adj[2] gain mirror entries, and cells [0][2] and [2][0] become 1.
4. Repeat the three writes for 1-3, 2-3, and 3-4. No write ever touches vertex 5.
5. The finished adjacency list is 0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3], 5:[]. It contains ten neighbor entries: exactly 2E = 10.
6. The matrix contains 36 cells because V² = 6² = 36. Its row for vertex 3 is [0,1,1,0,1,0], matching neighbors 1, 2, and 4 from the list.
7. Compute degree(3). The list reads len(adj[3]) = 3. The matrix sums row 3, also obtaining 3, but it inspects all six cells to do so.
8. Ask has_edge(3, 5). The list compares 1 with 5, then 2, then 4; the row ends after three probes, so the answer is False.
9. The matrix reads matrix[3][5]. That one cell is 0, so it returns the same False answer in one lookup.

On the canvas, the source edge stays visible while its list entries and symmetric matrix cells light up. During the query, the list cursor walks neighbor by neighbor; the matrix guides cross at one cell. The motion is not decoration. It is the cost model made visible.

Time and space complexity

Let V be the number of vertices, E the number of undirected edges, and degree(u) the number of neighbors of vertex u.

Let the workload choose. If your program asks millions of arbitrary edge-membership questions, a matrix may earn its space. If it mostly walks the neighbors that exist, an adjacency list avoids scanning a desert of zeros.

The list wins the usual sparse-graph argument because E is far smaller than V². The default needs six row heads and ten neighbor entries, while the matrix reserves 36 cells.

Dense K5 is the useful correction. A complete five-vertex graph has ten edges, so the list's logical term count is V + 2E = 5 + 20 = 25, exactly the matrix's V² = 25 cells. Those counts are not byte measurements; real arrays, pointers, and row objects have different overhead. They do show why the list's asymptotic space advantage disappears when E = Θ(V²).

Edge cases

• Singleton graph: one vertex, no edges. Its list row is empty, its 1 by 1 matrix contains zero, and degree(0) = 0.
• Isolated vertex: vertex 5 in the default has a real row and matrix row even though both contain no neighbors.
• Absent edge: has_edge(3, 5) returning False is normal data, not an error condition.
• Dense graph: Dense K5 removes the list's sparse-space advantage and makes a late list hit scan four neighbors.
• Self-loops and parallel edges: this lesson excludes both. Supporting them requires an explicit convention about diagonal cells and duplicate list entries.

Common mistakes

• Writing only one list direction. For an undirected edge u-v, both adj[u] and adj[v] must change.
• Writing only one matrix cell. An undirected adjacency matrix is symmetric, so [u][v] and [v][u] must agree.
• Claiming matrix space is O(E). The grid reserves V² cells even when almost every cell is zero.
• Scanning every vertex for a list query. has_edge(u, v) scans only adj[u], so its bound is O(degree(u)), not automatically O(V + E).
• Treating logical entries as bytes. V + 2E and V² explain growth rates. They do not claim that one list entry occupies the same memory as one matrix cell.