What are the ways to store graphs?
There are three main ways to store graphs:
1. Adjacency List
Each vertex stores a list of all the vertices it is connected to.
Example: For a graph with edges A-B, A-C, B-C
javascript
A: B, C
B: A, C
C: A, BPros:
- Memory-efficient for sparse graphs (few edges).
- Convenient for traversing a vertex's neighbors.
Cons:
- Looking up a specific edge can be slower than with a matrix.
2. Adjacency Matrix
Uses a square n×n matrix, where n is the number of vertices.
Cell [i][j] = 1 (or a weight) if there is an edge between i and j, otherwise 0.
Example:
javascript
A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]Pros:
- Fast edge-existence check (O(1)).
- Convenient for dense graphs (many edges).
Cons:
- Takes O(n²) memory, even if there are few connections.
3. Edge List
Simply stores a list of all edges as pairs (or triples, if weighted):
javascript
[(A, B), (A, C), (B, C)]or
javascript
[(A, B, 5), (B, C, 3), (A, C, 8)]Pros:
- Simple structure.
- Convenient for algorithms that work directly with edges (for example, Kruskal's).
Cons:
- Inconvenient for looking up a vertex's neighbors.
Summary:
| Method | Memory | Convenient for | Example use |
|---|---|---|---|
| Adjacency list | O(V + E) | traversals and pathfinding | Dijkstra, BFS, DFS algorithms |
| Adjacency matrix | O(V²) | fast connection checks | dense graphs |
| Edge list | O(E) | working with edges directly | Kruskal's algorithm |
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.