Graph Theory • Representations

Adjacency List

An Adjacency List represents a graph as a collection of linked lists or arrays. Each node stores a list of its direct neighbors, making it highly efficient for sparse graphs.

Try Interactive Simulator

Overview

Instead of a grid, we store only the edges that exist. Each vertex acts as a key to its own list of connected neighbors.

Space Efficiency

For a graph with many nodes but few edges (sparse), this saves massive amounts of memory compared to a matrix.

Edge Lookup

To check if Node A connects to Node B, we must scan through Node A's list. This is slower than the O(1) lookup of a matrix.

Implementation

Commonly implemented using arrays of lists, vectors, or hash maps depending on the programming language.