Graph Representations: Matrix and List | Data Structures

How do you physically store a graph in computer memory? The two primary representations are the Adjacency Matrix and the Adjacency List.

1. Adjacency Matrix

An Adjacency Matrix is a 2D grid of size V × V, where V is the number of vertices.

matrix[i][j] = 1 (or edge weight) if an edge exists from vertex i to vertex j.
matrix[i][j] = 0 if no edge exists.

Graph:
(0) --- (1)
 |
(2)

Adjacency Matrix:
      0  1  2
  0 [ 0, 1, 1 ]
  1 [ 1, 0, 0 ]
  2 [ 1, 0, 0 ]

Trade-offs:

Fast Edge Lookup: Checking if edge (u, v) exists takes O(1) time.
Heavy Space Waste: Requires O(V²) memory space, regardless of how few edges exist!
Finding all neighbors of vertex u takes O(V) time.

2. Adjacency List

An Adjacency List represents the graph as an array (or map) of linked lists or dynamic arrays, where adjList[u] contains only the vertices directly adjacent to u.

Adjacency List:
[0] -> [ 1, 2 ]
[1] -> [ 0 ]
[2] -> [ 0 ]

In Kotlin:

class Graph(val numVertices: Int) {
    val adjList: Array<MutableList<Int>> = Array(numVertices) { mutableListOf() }

    fun addEdge(u: Int, v: Int, bidirectional: Boolean = true) {
        adjList[u].add(v)
        if (bidirectional) {
            adjList[v].add(u)
        }
    }
}

Head-to-Head Comparison

Metric / Operation	Adjacency Matrix	Adjacency List
Memory Space	`O(V²)`	`O(V + E)`
Check if (u, v) is an edge	`O(1)`	`O(degree(u))`
Iterate over all neighbors of `u`	`O(V)` (Scans entire row)	`O(degree(u))`
Add a vertex	`O(V²)` (Reallocate matrix)	`O(1)`
Add an edge	`O(1)`	`O(1)`
Best Used For	Dense Graphs (`E ≈ V²`)	Sparse Graphs (`E ≪ V²`)

Which Should You Use in Production?

In almost all real-world applications (Google Maps, social networks, dependency graphs), graphs are sparse:

A user on Twitter has ~500 followers, not 500,000,000.
An intersection connects to 3 or 4 roads, not all 100,000 roads in the city.

Therefore, Adjacency Lists are the default choice in 99% of software systems.

Summary

Adjacency Matrix is an O(V²) 2D grid offering O(1) edge checks, best for dense graphs.
Adjacency List is an O(V + E) structure that stores only existing neighbors, making it optimal for sparse networks.