Graph Representation Lab
Represent the same simple graph as an adjacency matrix and an adjacency list. Compare sparse and dense presets, then step through an edge lookup or a neighbor scan to see where each representation spends its work.
Lists are sorted for reproducibility and scanned sequentially, without an early stop based on key order. Every Step advances each unfinished representation by one entry inspection.
Current comparison
Adjacency matrix
Adjacency list
The same graph
Cost model
| Operation | Matrix | List |
|---|---|---|
| Storage | Θ(V²) | Θ(V + E) |
| Edge lookup | Θ(1) | O(deg(u)) |
| Scan neighbors | Θ(V) | Θ(deg(u)) |
Neighbor-scan costs count inspected entries; an empty list still has constant setup overhead. List lookup has worst-case Θ(deg(u)) for nonempty lists. Header and pointer overhead depends on implementation; displayed storage counts are logical slots, not bytes.
For an undirected graph, each edge occupies two list entries. At high density both representations can use Θ(V²) storage. Constant-time matrix lookup can then be attractive, while sparse graphs save many slots with lists.