1. Understanding Graphs: Relationship Between Vertices and Edges¶
In data structures, a graph is composed of “vertices” (also called nodes) and “edges.” For example:
- In a social network, each user is a vertex, and “friendship” between users is an edge.
- In a city traffic map, each city is a vertex, and “roads” between cities are edges.
2. Adjacency Matrix: The Most Intuitive Storage Method¶
The adjacency matrix is the most basic way to store graphs and uses a 2D array. Here, rows and columns represent the vertices of the graph, and the value (0 or 1) indicates whether there is an edge between two vertices (1 = edge exists, 0 = no edge).
Example:
Suppose there are 3 vertices (0, 1, 2) with edges: 0-1 and 1-2.
The adjacency matrix is:
0 1 2
0 0 1 0
1 1 0 1
2 0 1 0
- The value
matrix[i][j]represents whether there is an edge between vertex i and vertex j. - For example,
matrix[0][1] = 1means there is an edge between vertex 0 and 1;matrix[2][1] = 1means there is an edge between vertex 2 and 1.
3. Adjacency List: “Neighbor List” Storage¶
The adjacency list is a more flexible storage method. For each vertex, it maintains a linked list (or dynamic array) to store all “neighbors” directly connected to that vertex.
Using the same example:
- Vertex 0 has neighbor 1 → 0: [1]
- Vertex 1 has neighbors 0 and 2 → 1: [0, 2]
- Vertex 2 has neighbor 1 → 2: [1]
In short: Each vertex is followed by its “neighbor list”. Isolated vertices (with no neighbors) have an empty adjacency list.
4. Comparison: Adjacency Matrix vs. Adjacency List¶
| Dimension | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space Complexity | Requires n² space (n = number of vertices). Always occupies n² positions regardless of the number of edges. |
Occupies only n + e space (e = number of edges). Only stores actual existing edges. |
| Edge Lookup | Directly access the 2D array, time O(1) (e.g., check if an edge exists between vertices i and j by matrix[i][j]). |
Traverse the adjacency list of vertex i, time O(degree(i)) (where degree(i) is the number of neighbors of vertex i). |
| Neighbor Traversal | Traverse the entire row (e.g., all neighbors of vertex i), time O(n) (checks all n positions regardless of whether edges exist). |
Traverse only the adjacency list, time O(degree(i)) (only accesses actual existing edges). |
5. Why is the Adjacency List Better?¶
Core Advantage: Efficiency for Sparse Graphs
In practice, most graphs are sparse (e.g., in social networks, a person’s friends are far fewer than the total number of users). For such cases:
- Adjacency Matrix wastes space (e.g., a graph with 1000 vertices and 1000 edges still occupies 1000×1000 = 1 million positions).
- Adjacency List only stores actual edges, saving space (1000+1000 = 2000 positions).
Exception: For dense graphs (e.g., complete graphs where every vertex connects to all others), the adjacency matrix may be more suitable (though this is rare).
6. Summary¶
The adjacency list is a “high-efficiency storage tool” for sparse graphs. It uses “neighbor lists” to store actual edges with minimal space and traverse neighbors faster. While the adjacency matrix is intuitive, the adjacency list is generally preferred in most practical scenarios (especially for sparse graphs).
In programming, the adjacency list is the mainstream storage method for graph problems (e.g., shortest paths, topological sorting) and is a core data structure beginners must master.
Quick Takeaway: An adjacency list is like a “friend list” for each vertex—more space-efficient and faster than the adjacency matrix’s “full-table” approach!