Representing a graph
A graph is a set of vertices connected by edges. Before running any algorithm you must choose how to store those edges in memory. The two standard choices are the adjacency list and the adjacency matrix.
Adjacency list
An adjacency list keeps, for each vertex, a collection of its neighbors. If vertex three connects to vertices one and five, then the list for three holds one and five.
- Uses memory proportional to the number of vertices plus edges, so it is compact for sparse graphs.
- Iterating over a vertex's neighbors is fast because you only touch real edges.
- Checking whether a specific edge exists may require scanning a neighbor collection.
Adjacency matrix
An adjacency matrix is a grid where the cell at row i and column j marks whether an edge runs from i to j.
- Edge existence checks are instant: just read one cell.
- Memory grows with the square of the vertex count, which wastes space on dense or large sparse graphs.
Most real systems pick the adjacency list because real graphs tend to be sparse.
Key idea
Use an adjacency list for sparse graphs to save memory, and a matrix when fast edge lookups on dense graphs matter more.