Graph (đồ thị) là một tập các đỉnh (vertices) được nối bởi các cạnh (edges). Hai cách biểu diễn tiêu chuẩn là adjacency list (danh sách kề — mỗi đỉnh lưu các láng giềng của nó) và adjacency matrix (ma trận kề — một lưới boolean V×V). Lựa chọn phụ thuộc vào mật độ (density) của graph.
Graph: 0 - 1
| |
2 - 3
Adjacency list: Adjacency matrix:
0: [1, 2] 0 1 2 3
1: [0, 3] 0 [0 1 1 0]
2: [0, 3] 1 [1 0 0 1]
3: [1, 2] 2 [1 0 0 1]
3 [0 1 1 0]
# Adjacency list (dict của các list) — ưu tiên cho graph thưa (sparse)
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1] # O(1) để lấy các láng giềng của một đỉnh
# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1 # tra cứu cạnh O(1)
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Không gian | O(V + E) | O(V²) |
| Cạnh có tồn tại? | O(degree) | O(1) |
| Duyệt láng giềng | O(degree) | O(V) |
| Tốt nhất cho | graph thưa | graph dày (dense) |
Hầu hết các graph thực tế (mạng xã hội, bản đồ đường, dependency graph) đều thưa (sparse), nên adjacency list tiết kiệm không gian khổng lồ và tăng tốc các phép duyệt như BFS/DFS.
Biết sự đánh đổi cho phép bạn chọn cách biểu diễn giữ cho các thuật toán graph của bạn hiệu quả thay vì vô tình dùng bộ nhớ O(V²).