Let’s first consider a scenario in daily life: cities connected by highways, where we need to know which cities are reachable from each other; or in a social network, who are your friends and who know each other through mutual connections. All these can be abstracted into the concept of a “graph.”
一、Basic Concepts of Graphs¶
In data structures, a Graph is a structure composed of a set of vertices (or nodes) and a set of edges. A vertex is a “point” in the graph, and an edge is the “line” connecting two vertices.
- Vertex: Also called a “node,” it is the basic unit of a graph. For example, each person in a social network is a vertex.
- Edge: The relationship connecting two vertices. Edges can be directed or undirected, and may have weights (e.g., the length of a highway or the price of a flight).
Classification of Graphs¶
Graphs come in many types. Beginners should understand the two most fundamental ones:
1. Directed Graph: Edges have directionality. For example, a “follow” relationship on Weibo (if you follow someone, it doesn’t mean they follow you).
2. Undirected Graph: Edges have no directionality. For example, a “friend” relationship on WeChat (bidirectional).
Additionally, there are weighted graphs and unweighted graphs:
- Weighted Graph: Edges have weights (numerical values), e.g., “The distance from City A to City B is 100 kilometers.”
- Unweighted Graph: Edges have no weights, only connection relationships (e.g., friend relationships in a social network, where we only care about whether someone is acquainted).
二、Adjacency List: Why Do We Need It?¶
There are many ways to represent a graph, with the most common being the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array where adj[i][j] indicates whether there is an edge between vertex i and j (1 for yes, 0 for no). However, the adjacency matrix has a drawback: when the graph is sparse (the number of edges is much smaller than the square of the number of vertices), it wastes a lot of space. For example, a graph with 1000 vertices requires 1000×1000=1,000,000 positions in the adjacency matrix, but if there are only 100 edges, most positions will be 0.
The adjacency list is a more efficient representation: it only stores the actual edges, making it more space-efficient. The core idea is: Each vertex corresponds to a list that stores all vertices directly connected to it.
三、Specific Structure of the Adjacency List¶
Taking an undirected graph as an example, suppose the vertices are 0, 1, 2, 3, with the following connections:
- Vertex 0 is connected to 1, 2, 3
- Vertex 1 is connected to 0, 2
- Vertex 2 is connected to 0, 1, 3
- Vertex 3 is connected to 0, 2
The adjacency list can be structured as:
Adjacency list of Vertex 0: [1, 2, 3] # 0 is connected to 1, 2, 3
Adjacency list of Vertex 1: [0, 2] # 1 is connected to 0, 2
Adjacency list of Vertex 2: [0, 1, 3] # 2 is connected to 0, 1, 3
Adjacency list of Vertex 3: [0, 2] # 3 is connected to 0, 2
In array form, the adjacency list can be written as:
adj = [
[1, 2, 3], # Adjacent vertices of Vertex 0
[0, 2], # Adjacent vertices of Vertex 1
[0, 1, 3], # Adjacent vertices of Vertex 2
[0, 2] # Adjacent vertices of Vertex 3
]
Adjacency List for Directed Graphs¶
For a directed graph (e.g., Vertex 0→1, Vertex 1→2, Vertex 2→0), the adjacency list only stores the “outgoing edges” of each vertex:
Adjacency list of Vertex 0: [1, 2] # 0 points to 1 and 2
Adjacency list of Vertex 1: [2] # 1 points to 2
Adjacency list of Vertex 2: [0] # 2 points to 0
Adjacency list of Vertex 3: [] # 3 has no outgoing edges
四、Implementation of the Adjacency List (Undirected Graph Example)¶
When implementing an adjacency list in code, the most common approach is:
- Use an array (or list) to store the adjacency information of all vertices, where each element in the array corresponds to a vertex.
- Use a list (or linked list) to store the adjacency information for each vertex.
Python Implementation Example¶
# Assume there are 4 vertices (0, 1, 2, 3)
num_vertices = 4
adj = [[] for _ in range(num_vertices)] # Initialize adjacency list with empty lists for each vertex
# Add edges (for undirected graphs, each edge (u, v) must be added in both directions)
edges = [(0,1), (0,2), (0,3), (1,2), (2,3)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # Add bidirectionally for undirected graphs
print(adj) # Output: [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
Adjacency List for Weighted Graphs¶
For a weighted graph, each element in the adjacency list can store a tuple of “adjacent vertex + weight”:
# Example of a weighted graph: Edge from Vertex 0 to 1 has weight 5, 0 to 2 has weight 3, etc.
edges = [(0,1,5), (0,2,3), (0,3,8), (1,2,2), (2,3,1)]
adj_weighted = [[] for _ in range(num_vertices)]
for u, v, w in edges:
adj_weighted[u].append((v, w))
adj_weighted[v].append((u, w)) # Bidirectional for undirected graphs
print(adj_weighted)
# Output: [[(1, 5), (2, 3), (3, 8)], [(0, 5), (2, 2)], [(0, 3), (1, 2), (3, 1)], [(0, 8), (2, 1)]]
五、Advantages and Disadvantages of the Adjacency List¶
- Advantages:
- High space efficiency: Only stores actual edges, with space complexity O(V + E) (V = number of vertices, E = number of edges), suitable for sparse graphs.
- Easy to traverse: Can quickly access all adjacent vertices of a given vertex.
-
Easy to insert and delete edges.
-
Disadvantages:
- Checking if there is an edge between two vertices requires traversing the adjacency list, with time complexity O(d) (d = degree of the vertex).
- For complete graphs (edges close to V²), the adjacency list may be less efficient than the adjacency matrix (though this is rare).
Summary¶
Graphs are a crucial concept in data structures, and the adjacency list is an efficient representation method, especially for sparse graphs. Mastering the adjacency list not only helps understand the storage logic of graphs but also lays the foundation for learning graph traversal algorithms (e.g., BFS, DFS) and shortest path algorithms.
We hope this guide helps you quickly get started with the basic concepts of graphs and the adjacency list representation. In practice, try implementing simple graph operations using adjacency lists, such as traversing all adjacent vertices or checking if two vertices are connected.