Adjacency List: Structure with Arrays
You'll learn how to represent a graph using an array of lists, where each vertex keeps track of its neighbors.
The Core Idea
Instead of using a matrix to represent connections (which we covered in adjacency matrices), we can use an array of lists. Each index in the array represents a vertex, and the list at that index contains all the vertices directly connected to it.
Think of it like a contact list on your phone: each person (vertex) has their own entry, and under their name is a list of people they're friends with (adjacent vertices). You don't store information about people they aren't friends with—only the actual connections.
How It Works
If you have a graph with n vertices numbered 0 to n-1:
- Create an array of size
n - Each array slot holds a list (or collection) of adjacent vertices
- For vertex
i,array[i]contains all vertices thaticonnects to
Example: For an undirected graph where vertex 0 connects to vertices 1 and 3:
array[0]→ list containing[1, 3]array[1]→ list containing[0](if 1 only connects back to 0)array[3]→ list containing[0]
For directed graphs, you only store outgoing edges. For weighted graphs, you'd store pairs of (vertex, weight) instead of just vertex numbers.
Why Use This Structure?
This representation is space-efficient for sparse graphs (graphs with few edges), storing only actual connections rather than all possible pairs. It also makes operations like "find all neighbors of vertex v" very fast—just look at array[v].
Key Takeaway: An adjacency list uses an array of lists to represent graphs efficiently by storing only actual connections, making it ideal for sparse graphs where each vertex connects to relatively few others.