Two ways to store a graph
A graph is a set of vertices joined by edges. Before running any algorithm you must decide how those edges live in memory. The two classic choices are the adjacency list and the adjacency matrix.
Adjacency list
- Each vertex keeps a list of its neighbours.
- Memory grows with the number of vertices plus the number of edges, so it is compact for sparse graphs.
- Visiting all neighbours of a vertex is cheap because you only walk that vertex's list.
- Checking whether a single specific edge exists means scanning a list.
Adjacency matrix
- A grid of vertices by vertices, where each cell records whether an edge is present.
- Memory grows with the square of the vertex count, which is wasteful when edges are few.
- Looking up one specific edge is a constant time cell read.
- Iterating one vertex's neighbours still costs a full row scan even if it has few edges.
Most real graphs are sparse, so adjacency lists dominate practical code. Dense graphs, or algorithms that constantly ask "is there an edge here", can favour the matrix.
Key idea
Pick the adjacency list for sparse graphs and easy neighbour walks, and the adjacency matrix when the graph is dense or you need instant single edge lookups.