Bài học

Biểu diễn đồ thị: danh sách kề và ma trận kề

Mục tiêu bài học

Sau bài này, em đọc đúng khuôn input chuẩn của một bài đồ thị đề HSG QG/VOI ( $n$ , $m$ rồi $m$ dòng cạnh), dựng được cả danh sách kề lẫn ma trận kề từ input đó, và — quan trọng hơn cả việc dựng được — chọn đúng cấu trúc nào cho đúng bài, dựa trên ràng buộc $V$ , $E$ mà đề cho. Chọn sai cấu trúc là lý do phổ biến nhất khiến một bài đồ thị vốn dễ bị MLE (Memory Limit Exceeded) ngay ở bước đọc dữ liệu, trước khi thuật toán kịp chạy.

Sau bài này, em đọc đúng khuôn input chuẩn của một bài đồ thị đề HSG QG/VOI ($n$, $m$ rồi $m$ dòng cạnh), dựng được cả danh sách kề lẫn ma trận kề từ input đó, và — quan trọng hơn cả việc dựng được — **chọn đúng cấu trúc nào cho đúng bài**, dựa trên ràng buộc $V$, $E$ mà đề cho. Chọn sai cấu trúc là lý do phổ biến nhất khiến một bài đồ thị vốn dễ bị MLE (Memory Limit Exceeded) ngay ở bước đọc dữ liệu, trước khi thuật toán kịp chạy.

Cần nhớ trước

Cần nhớ trước: khái niệm đỉnh, cạnh, bậc của đỉnh (đã học ở Tin học 11); mảng và danh sách (list) trong Python; kiểu dữ liệu và độ phức tạp bộ nhớ $O(\cdot)$ .

So với mức chuẩn: đề kiểm tra thông thường cho đồ thị nhỏ — $V$ và $E$ chỉ vài chục — nên bất kỳ cách lưu nào cũng chạy được, và đề thường cho sẵn cấu trúc (ví dụ in sẵn ma trận). Đề HSG QG/VOI thì khác: $V$ , $E$ được cho dưới dạng ràng buộc lớn ( $V \le 10^5$ , $E \le 2\times 10^5$ là phổ biến), và chính học sinh phải quyết định dùng cấu trúc nào — quyết định sai làm chương trình không chạy nổi dù thuật toán đúng.

**So với mức chuẩn:** đề kiểm tra thông thường cho đồ thị nhỏ — $V$ và $E$ chỉ vài chục — nên bất kỳ cách lưu nào cũng chạy được, và đề thường cho sẵn cấu trúc (ví dụ in sẵn ma trận). Đề HSG QG/VOI thì khác: $V$, $E$ được cho dưới dạng ràng buộc lớn ($V \le 10^5$, $E \le 2\times 10^5$ là phổ biến), và **chính học sinh phải quyết định** dùng cấu trúc nào — quyết định sai làm chương trình không chạy nổi dù thuật toán đúng.

Tình huống mở đầu — vì sao một lựa chọn tưởng vô hại lại làm sập chương trình

Một đề bài cho $n \le 10^5$ đỉnh, $m \le 2\times 10^5$ cạnh, rồi hỏi $10^5$ truy vấn dạng "liệt kê các đỉnh kề của $u$ ". Một học sinh quen tay khai báo adj = [[0] * n for _ in range(n)] — ma trận kề — để "cho chắc, tra cứu cạnh nào cũng nhanh". Chương trình bị Memory Limit Exceeded ngay khi vừa khai báo mảng, chưa đọc xong input, vì $n^2 = 10^{10}$ ô nhớ — không máy chấm nào cấp đủ RAM cho mức đó. Vấn đề không nằm ở thuật toán truy vấn — nó nằm ở việc chọn cấu trúc lưu trữ mà không nhìn ràng buộc $V$ .

Một đề bài cho $n \le 10^5$ đỉnh, $m \le 2\times 10^5$ cạnh, rồi hỏi $10^5$ truy vấn dạng "liệt kê các đỉnh kề của $u$". Một học sinh quen tay khai báo `adj = [[0] * n for _ in range(n)]` — ma trận kề — để "cho chắc, tra cứu cạnh nào cũng nhanh". Chương trình bị Memory Limit Exceeded ngay khi vừa khai báo mảng, chưa đọc xong input, vì $n^2 = 10^{10}$ ô nhớ — không máy chấm nào cấp đủ RAM cho mức đó. Vấn đề không nằm ở thuật toán truy vấn — nó nằm ở việc chọn cấu trúc lưu trữ mà không nhìn ràng buộc $V$.

Ý tưởng cốt lõi — so bộ nhớ và tốc độ truy vấn trước khi viết dòng code đầu tiên

Hai cấu trúc chuẩn có đánh đổi ngược nhau:

Danh sách kề (adjacency list) — mỗi đỉnh giữ một danh sách các đỉnh kề. Bộ nhớ $O(V+E)$ (cụ thể: $2E$ phần tử cho đồ thị vô hướng, vì mỗi cạnh xuất hiện ở cả hai đầu). Duyệt toàn bộ đỉnh kề của $u$ tốn $O(\deg(u))$ — đúng bằng số cạnh cần xét, không hơn.
Ma trận kề (adjacency matrix) — bảng $V \times V$ , ô $(u,v)$ đánh dấu có cạnh hay không. Bộ nhớ $O(V^2)$ bất kể đồ thị thưa hay dày. Tra cứu "có cạnh $(u,v)$ không?" chỉ tốn $O(1)$ — tra thẳng một ô.

Quy tắc chọn: nếu $E \ll V^2$ (đồ thị thưa, phổ biến ở đề HSG QG khi $V$ lớn) — danh sách kề luôn thắng, vì ma trận sẽ lãng phí gần như toàn bộ ô nhớ cho các cặp không có cạnh. Nếu $V$ nhỏ (cỡ vài trăm) và đề cần tra cứu cạnh lặp lại nhiều lần — ma trận kề đơn giản hơn để cài đặt và đủ nhanh.

Hai cấu trúc chuẩn có đánh đổi ngược nhau: - **Danh sách kề (adjacency list)** — mỗi đỉnh giữ một danh sách các đỉnh kề. Bộ nhớ $O(V+E)$ (cụ thể: $2E$ phần tử cho đồ thị vô hướng, vì mỗi cạnh xuất hiện ở cả hai đầu). Duyệt toàn bộ đỉnh kề của $u$ tốn $O(\deg(u))$ — đúng bằng số cạnh cần xét, không hơn. - **Ma trận kề (adjacency matrix)** — bảng $V \times V$, ô $(u,v)$ đánh dấu có cạnh hay không. Bộ nhớ $O(V^2)$ bất kể đồ thị thưa hay dày. Tra cứu "có cạnh $(u,v)$ không?" chỉ tốn $O(1)$ — tra thẳng một ô. Quy tắc chọn: nếu $E \ll V^2$ (đồ thị **thưa**, phổ biến ở đề HSG QG khi $V$ lớn) — danh sách kề luôn thắng, vì ma trận sẽ lãng phí gần như toàn bộ ô nhớ cho các cặp không có cạnh. Nếu $V$ nhỏ (cỡ vài trăm) và đề cần tra cứu cạnh lặp lại nhiều lần — ma trận kề đơn giản hơn để cài đặt và đủ nhanh.

Ví dụ

Ví dụ 1 — Dựng danh sách kề từ input chuẩn

1
Đề chuẩn thường cho sẵn cấu trúc để học sinh chỉ việc dùng. Ở đây đề chỉ cho $n=6$ , $m=7$ rồi $7$ dòng cạnh — học sinh phải tự dựng cấu trúc, và một lựa chọn sai (ví dụ quên đồ thị vô hướng cần thêm cạnh cả hai chiều) sẽ cho kết quả sai ở MỌI thuật toán chạy sau đó, dù thuật toán viết đúng.
Đề chuẩn thường cho sẵn cấu trúc để học sinh chỉ việc dùng. Ở đây đề chỉ cho $n=6$, $m=7$ rồi $7$ dòng cạnh — học sinh phải tự dựng cấu trúc, và một lựa chọn sai (ví dụ quên đồ thị vô hướng cần thêm cạnh cả hai chiều) sẽ cho kết quả sai ở MỌI thuật toán chạy sau đó, dù thuật toán viết đúng.
2
$n=6$ đỉnh (đánh số $1..6$ ), $m=7$ cạnh vô hướng: $(1,2), (1,3), (2,3), (2,4), (3,5), (4,5), (4,6)$ . Dựng danh sách kề, mỗi danh sách sắp tăng dần.
$n=6$ đỉnh (đánh số $1..6$), $m=7$ cạnh vô hướng: $(1,2), (1,3), (2,3), (2,4), (3,5), (4,5), (4,6)$. Dựng danh sách kề, mỗi danh sách sắp tăng dần.
3
```
n, m = 6, 7
edges = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6)]
adj = [[] for _ in range(n + 1)]  # 1-indexed, adj[0] bỏ trống
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)   # đồ thị VÔ HƯỚNG: thêm cả hai chiều
for u in range(1, n + 1):
    adj[u].sort()
```
Chạy đoạn trên với đúng $7$ cạnh của đề, ta được: adj[1]=[2,3], adj[2]=[1,3,4], adj[3]=[1,2,5], adj[4]=[2,5,6], adj[5]=[3,4], adj[6]=[4].
```python n, m = 6, 7 edges = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6)] adj = [[] for _ in range(n + 1)] # 1-indexed, adj[0] bỏ trống for u, v in edges: adj[u].append(v) adj[v].append(u) # đồ thị VÔ HƯỚNG: thêm cả hai chiều for u in range(1, n + 1): adj[u].sort() ``` Chạy đoạn trên với đúng $7$ cạnh của đề, ta được: `adj[1]=[2,3]`, `adj[2]=[1,3,4]`, `adj[3]=[1,2,5]`, `adj[4]=[2,5,6]`, `adj[5]=[3,4]`, `adj[6]=[4]`.
4
Tổng độ dài các danh sách phải bằng $2m = 14$ : đếm trực tiếp $2+3+3+3+2+1 = 14$ . (1) Khớp — mỗi cạnh vô hướng đóng góp đúng $2$ vào tổng độ dài, không thừa không thiếu.
Tổng độ dài các danh sách phải bằng $2m = 14$: đếm trực tiếp $2+3+3+3+2+1 = 14$. (1) Khớp — mỗi cạnh vô hướng đóng góp đúng $2$ vào tổng độ dài, không thừa không thiếu.
5
Bậc của đỉnh $u$ chính là $\deg(u) = |\text{adj}[u]|$ — không cần đếm riêng, danh sách kề đã "miễn phí" cho ta thông tin bậc. Vậy danh sách kề của đồ thị mẫu là adj[1]=[2,3], adj[2]=[1,3,4], adj[3]=[1,2,5], adj[4]=[2,5,6], adj[5]=[3,4], adj[6]=[4], tổng $14$ phần tử.
Bậc của đỉnh $u$ chính là $\deg(u) = |\text{adj}[u]|$ — không cần đếm riêng, danh sách kề đã "miễn phí" cho ta thông tin bậc. Vậy danh sách kề của đồ thị mẫu là `adj[1]=[2,3]`, `adj[2]=[1,3,4]`, `adj[3]=[1,2,5]`, `adj[4]=[2,5,6]`, `adj[5]=[3,4]`, `adj[6]=[4]`, tổng $14$ phần tử.

Ma trận kề cho đúng đồ thị ở Ví dụ 1 — đối xứng qua đường chéo vì đồ thị vô hướng.

Ví dụ

Ví dụ 2 — Dựng ma trận kề và so bộ nhớ với danh sách kề

1
```
M = [[0] * (n + 1) for _ in range(n + 1)]
for u, v in edges:
    M[u][v] = 1
    M[v][u] = 1
```
Với đúng $7$ cạnh của Ví dụ 1, ma trận kề $6\times 6$ là bảng ở hình minh hoạ bên dưới — đối xứng qua đường chéo chính vì đồ thị vô hướng: $M[u][v]=M[v][u]$ .
```python M = [[0] * (n + 1) for _ in range(n + 1)] for u, v in edges: M[u][v] = 1 M[v][u] = 1 ``` Với đúng $7$ cạnh của Ví dụ 1, ma trận kề $6\times 6$ là bảng ở hình minh hoạ bên dưới — đối xứng qua đường chéo chính vì đồ thị vô hướng: $M[u][v]=M[v][u]$.
2
Danh sách kề lưu $2m = 14$ số nguyên. Ma trận kề lưu $n^2 = 36$ ô, bất kể có bao nhiêu cạnh thật sự tồn tại. Với $n=6$ khác biệt chưa đáng kể — nhưng thử phóng ràng buộc lên đúng mức đề HSG QG hay cho: $n = 10^5$ . Danh sách kề với $m \le 2\times 10^5$ vẫn chỉ cỡ $4\times 10^5$ số nguyên (vài MB). Ma trận kề cần $n^2 = 10^{10}$ ô — dù mỗi ô chỉ $1$ byte cũng đã cỡ $10$ GB, vượt xa RAM một máy chấm cấp cho một bài. (1)
Danh sách kề lưu $2m = 14$ số nguyên. Ma trận kề lưu $n^2 = 36$ ô, bất kể có bao nhiêu cạnh thật sự tồn tại. Với $n=6$ khác biệt chưa đáng kể — nhưng thử phóng ràng buộc lên đúng mức đề HSG QG hay cho: $n = 10^5$. Danh sách kề với $m \le 2\times 10^5$ vẫn chỉ cỡ $4\times 10^5$ số nguyên (vài MB). Ma trận kề cần $n^2 = 10^{10}$ ô — dù mỗi ô chỉ $1$ byte cũng đã cỡ $10$ GB, vượt xa RAM một máy chấm cấp cho một bài. (1)
3
Từ (1): với đồ thị thưa và $V$ lớn, ma trận kề không chỉ chậm hơn mà còn không cấp phát nổi — đây không phải vấn đề tối ưu, mà là giới hạn cứng của bộ nhớ. Vậy với $V \le 10^5$ , $E \le 2\times 10^5$ như đề HSG QG hay cho, danh sách kề là lựa chọn bắt buộc, không phải sở thích cài đặt.
Từ (1): với đồ thị thưa và $V$ lớn, ma trận kề không chỉ chậm hơn mà còn **không cấp phát nổi** — đây không phải vấn đề tối ưu, mà là giới hạn cứng của bộ nhớ. Vậy với $V \le 10^5$, $E \le 2\times 10^5$ như đề HSG QG hay cho, danh sách kề là lựa chọn bắt buộc, không phải sở thích cài đặt.

Trên đúng đồ thị mẫu (V=6, E=7). Khoảng cách này giãn ra hàng tỉ lần khi V tăng tới 10^5.

Mở rộng dành cho HSG — danh sách cạnh cho thuật toán chỉ duyệt cạnh một lần

Chương trình THPT không dạy riêng một cấu trúc thứ ba, nhưng đề HSG QG hay gặp thuật toán chỉ cần duyệt toàn bộ cạnh đúng một lần — không cần tra cứu "đỉnh $u$ kề những đỉnh nào" lặp lại. Ví dụ điển hình là thuật toán Kruskal tìm cây khung nhỏ nhất (sẽ học ở Course 4): thuật toán chỉ cần sắp xếp mọi cạnh theo trọng số rồi xét lần lượt. Dựng cả danh sách kề lẫn ma trận kề cho việc này là lãng phí bộ nhớ không cần thiết — chỉ cần một danh sách cạnh (edge list): mảng các bộ $(u, v)$ hoặc $(w, u, v)$ nếu có trọng số $w$ .

Chương trình THPT không dạy riêng một cấu trúc thứ ba, nhưng đề HSG QG hay gặp thuật toán chỉ cần duyệt **toàn bộ cạnh đúng một lần** — không cần tra cứu "đỉnh $u$ kề những đỉnh nào" lặp lại. Ví dụ điển hình là thuật toán Kruskal tìm cây khung nhỏ nhất (sẽ học ở Course 4): thuật toán chỉ cần sắp xếp mọi cạnh theo trọng số rồi xét lần lượt. Dựng cả danh sách kề lẫn ma trận kề cho việc này là lãng phí bộ nhớ không cần thiết — chỉ cần một **danh sách cạnh** (edge list): mảng các bộ $(u, v)$ hoặc $(w, u, v)$ nếu có trọng số $w$.

Ví dụ

Ví dụ 3 — Danh sách cạnh (Mở rộng dành cho HSG)

edge_list = [(u, v) for u, v in edges]  # chỉ 7 bộ, không nhân đôi
# nếu có trọng số: edge_list = [(w, u, v) for w, u, v in weighted_edges]
# rồi sort theo trọng số khi cần (Kruskal, Course 4):
# edge_list.sort()

2
Danh sách cạnh chỉ lưu đúng $m$ bộ (không nhân đôi như danh sách kề vô hướng), nhẹ nhất trong ba cấu trúc — nhưng đổi lại không trả lời được "đỉnh $u$ kề những đỉnh nào" một cách trực tiếp. Vậy chọn danh sách cạnh khi và chỉ khi thuật toán thật sự chỉ cần duyệt cạnh, không cần tra cứu theo đỉnh.
Danh sách cạnh chỉ lưu đúng $m$ bộ (không nhân đôi như danh sách kề vô hướng), nhẹ nhất trong ba cấu trúc — nhưng đổi lại **không** trả lời được "đỉnh $u$ kề những đỉnh nào" một cách trực tiếp. Vậy chọn danh sách cạnh khi và chỉ khi thuật toán thật sự chỉ cần duyệt cạnh, không cần tra cứu theo đỉnh.

Chỗ hay mất điểm

Quên đồ thị VÔ HƯỚNG cần thêm cạnh vào danh sách kề của CẢ HAI đầu là lỗi đứng đầu danh sách — chỉ thêm một chiều làm BFS/DFS sau này duyệt thiếu, và lỗi này thường không lộ ra ở test nhỏ đối xứng ngẫu nhiên. Kế đó là khai báo ma trận kề cỡ $V \times V$ khi $V$ đã lên tới $10^4$ trở lên mà không ước lượng bộ nhớ trước, khiến chương trình chết ngay ở dòng khai báo, trước khi thuật toán kịp chạy dòng nào. Còn lẫn lộn đỉnh đánh số từ $0$ hay từ $1$ giữa lúc đọc input và lúc dùng mảng — lệch chỉ số (off-by-one) — vẫn là lỗi runtime phổ biến nhất của mọi bài đồ thị, không riêng gì bài này.