Hong Life CalculatorsUnderstanding the graph memory calculator — concept and principle
A graph can be stored as an adjacency matrix (a V × V grid that marks every possible edge) or as adjacency lists (each vertex keeps only the neighbors it actually has). This calculator estimates the memory of both layouts and the graph's density, so you can choose a representation before loading a large network, road map or social graph.
How it is calculated
- Adjacency matrix: V² bits ÷ 8 ÷ 10⁹ GB, assuming 1 bit per cell.
- Adjacency list: (V + 2E) × bytes per entry ÷ 10⁶ MB. Each undirected edge appears in both endpoints' lists (2E entries), plus one offset entry per vertex.
- Density: E ÷ (V(V − 1) ÷ 2) × 100%, the share of all possible undirected edges that exist.
The principle
A matrix reserves a cell for every pair of vertices, whether or not they are connected, so its size grows with V² and does not depend on E. Adjacency lists grow with V + E. The compact form counted here is like compressed sparse row (CSR): an offsets array with one entry per vertex and a single neighbor array. Real-world graphs are usually sparse; each vertex has a handful to a few thousand neighbors, while V − 1 neighbors are possible, so lists are typically far smaller. A matrix wins only when the graph is dense or when you need constant-time "is u connected to v?" checks.
Worked example
- Inputs: V = 100,000, E = 1,000,000, 4 bytes per entry.
- Matrix: 100,000² = 10¹⁰ bits ÷ 8 = 1.25 × 10⁹ bytes = 1.25 GB.
- List: (100,000 + 2 × 1,000,000) × 4 = 8,400,000 bytes = 8.4 MB.
- Density: 1,000,000 ÷ (100,000 × 99,999 ÷ 2) = 1,000,000 ÷ 4,999,950,000 ≈ 0.02%.
The list is about 150 times smaller, even though the matrix uses only one bit per cell.
| Vertices | Adjacency matrix (GB, 1 bit) |
|---|---|
| 25,000 | 0.078125 |
| 50,000 | 0.3125 |
| 75,000 | 0.703125 |
| 100,000 | 1.25 |
| 125,000 | 1.953125 |
| 150,000 | 2.8125 |
| 200,000 | 5 |
How to read the result
Density near 0% means a sparse graph: use lists. Bit-matrix and list sizes are equal around 2E × 32 ≈ V² for 4-byte entries, i.e. at a density of roughly 3%; above that, and especially above 10–20%, a matrix becomes competitive. Average degree 2E ÷ V (here 20) is another quick check.
Common mistakes
- Using V + 2E for directed graphs; a directed graph stores each edge once, so use V + E.
- Forgetting edge weights, which add another value per entry.
- Assuming 4-byte IDs suffice for more than about 4.29 billion vertices; beyond that, use 8 bytes.
Frequently asked questions
When should I use an adjacency matrix?
For small or dense graphs, or algorithms such as Floyd–Warshall that touch every pair anyway.
Why GB for one and MB for the other?
The units follow typical sizes; both use decimal units (1 GB = 10⁹ bytes, 1 MB = 10⁶ bytes).
How do I store a directed graph's incoming edges?
Keep a second CSR for the reverse graph, which doubles the list memory.
Sources: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (representations of graphs) · R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley (graph representations)