Đồ thị (danh sách kề, ma trận kề)

Đồ thị $G=(V,E)$ gồm tập đỉnh $V$ và tập cạnh $E$ nối các đỉnh. Hầu hết bài toán đồ thị (tìm đường, đếm thành phần liên thông, duyệt DFS/BFS, đường đi ngắn nhất...) đều bắt đầu bằng câu hỏi: lưu đồ thị trong bộ nhớ thế nào? Cách lưu quyết định cả tốc độ lẫn dung lượng. Hai cách phổ biến nhất là danh sách kề (adjacency list) và ma trận kề (adjacency matrix). Chọn đúng cách giúp duyệt toàn bộ đồ thị trong $O(V+E)$ thay vì $O(V^2)$, và tiết kiệm bộ nhớ từ $O(V^2)$ xuống $O(V+E)$ với đồ thị thưa.

Ý tưởng / Trực giác

Một đồ thị thực chất chỉ là câu trả lời cho hai loại truy vấn:

1. "Đỉnh $u$ có những hàng xóm nào?" — cần khi duyệt (DFS/BFS, Dijkstra...). Đây là truy vấn xảy ra nhiều nhất.
2. "Có cạnh $u\to v$ không?" — cần khi kiểm tra quan hệ giữa hai đỉnh cụ thể.

Hai cách biểu diễn tối ưu cho hai loại truy vấn khác nhau:

• Danh sách kề: với mỗi đỉnh $u$ ta lưu một danh sách các đỉnh kề. Trả lời truy vấn (1) cực nhanh — chỉ cần đọc danh sách. Tổng dung lượng đúng bằng số cạnh, nên rất tiết kiệm với đồ thị thưa (số cạnh nhỏ, $E\ll V^2$), vốn là đa số bài thi.
• Ma trận kề: dùng bảng $V\times V$, ô $(u,v)=1$ nếu có cạnh. Trả lời truy vấn (2) trong $O(1)$, nhưng luôn tốn $O(V^2)$ bộ nhớ dù đồ thị có ít cạnh — chỉ dùng được khi $V$ nhỏ (cỡ $\le 1000$).

Vì sao danh sách kề là lựa chọn mặc định? Bởi đa số thuật toán đồ thị (DFS, BFS, Dijkstra, topo-sort...) chỉ cần duyệt hàng xóm chứ hiếm khi hỏi "có cạnh không". Với danh sách kề, tổng công duyệt toàn bộ là ${\sum }_u\mathrm{deg}(u)=2E$ (đồ thị vô hướng) — mỗi cạnh được "chạm" đúng hai lần, cho ra $O(V+E)$. Ma trận kề bắt buộc quét cả hàng $V$ phần tử để tìm hàng xóm, nên duyệt toàn đồ thị tốn $O(V^2)$ dù đồ thị thưa.

Ví dụ chạy tay

Xét đồ thị vô hướng 5 đỉnh (đánh số $1.\mathrm{.5}$), 4 cạnh, đọc theo thứ tự:

Cạnh: (1,2) (1,3) (2,4) (3,4)

        1
       / \
      2   3
       \ /
        4        5  (đỉnh 5 cô lập)

Xây danh sách kề — mỗi cạnh $(u,v)$ thêm $v$ vào adj[u] và $u$ vào adj[v] (vô hướng nên hai chiều):

đọc (1,2):  adj[1]=[2]        adj[2]=[1]
đọc (1,3):  adj[1]=[2,3]      adj[3]=[1]
đọc (2,4):  adj[2]=[1,4]      adj[4]=[2]
đọc (3,4):  adj[3]=[1,4]      adj[4]=[2,3]

Kết quả:
adj[1] = [2, 3]
adj[2] = [1, 4]
adj[3] = [1, 4]
adj[4] = [2, 3]
adj[5] = []          ← đỉnh cô lập: danh sách rỗng

Cùng đồ thị, ma trận kề $A$ ($A[u][v]=1$ nếu có cạnh):

      v=1  2  3  4  5
u=1 [  0  1  1  0  0 ]
u=2 [  1  0  0  1  0 ]
u=3 [  1  0  0  1  0 ]
u=4 [  0  1  1  0  0 ]
u=5 [  0  0  0  0  0 ]   ← cả hàng + cả cột toàn 0

Nhận xét: ma trận đối xứng vì đồ thị vô hướng ($A[u][v]=A[v][u]$). Đỉnh cô lập 5 chiếm trọn một hàng và một cột toàn $0$ — lãng phí khi $V$ lớn. Với chỉ 4 cạnh nhưng ma trận vẫn dùng $25$ ô, còn danh sách kề chỉ lưu $2\times 4=8$ phần tử.

Duyệt hàng xóm của đỉnh 4:

Danh sách kề:  đọc thẳng adj[4] = [2, 3]   → 2 bước, đúng deg(4)
Ma trận kề:    quét hàng u=4: A[4][1..5]=0,1,1,0,0 → 5 bước (cả V cột)

Cài đặt

Danh sách kề (C++) — cách dùng phổ biến nhất

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;                    // n đỉnh, m cạnh
    cin >> n >> m;

    // adj[u] = danh sách các đỉnh kề với u.
    // Dùng n+1 để đánh số đỉnh từ 1..n cho tiện (bỏ chỉ số 0).
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);     // BỎ dòng này nếu đồ thị CÓ HƯỚNG
    }

    // Ví dụ duyệt toàn bộ hàng xóm của mọi đỉnh — tổng O(V+E)
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            /* xử lý cạnh u-v */;
}

Danh sách kề có trọng số (C++)

// Mỗi phần tử là cặp (đỉnh_kề, trọng_số)
vector<vector<pair<int,int>>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});    // bỏ nếu có hướng
}

// Duyệt: for (auto [v, w] : adj[u]) ...

Ma trận kề (C++)

// Chỉ khả thi khi n nhỏ (n <= ~1000 -> 10^6 ô int là ổn).
// Mảng toàn cục tự khởi tạo 0; nếu khai báo cục bộ nhớ {} để zero-init.
static int A[1005][1005];

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    A[u][v] = 1;
    A[v][u] = 1;                 // bỏ nếu có hướng
}

// Kiểm tra cạnh u-v trong O(1):  if (A[u][v]) ...

Danh sách kề (Python)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]      # đánh số 1..n
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)                  # bỏ nếu có hướng

Độ phức tạp

Vì sao:

• Bộ nhớ danh sách kề $O(V+E)$: mỗi đỉnh tốn một danh sách (tổng $V$ ô khung), mỗi cạnh được lưu hai lần (vô hướng) hoặc một lần (có hướng), tổng các phần tử là $O(E)$.
• Bộ nhớ ma trận kề $O(V^2)$: bảng $V\times V$ cố định, không phụ thuộc số cạnh — đây là điểm yếu chí mạng với đồ thị thưa. Khi $V={10}^5$, ma trận cần ${10}^{10}$ ô — bất khả thi; chỉ danh sách kề dùng được.
• Duyệt toàn bộ $O(V+E)$ với danh sách kề: mỗi cạnh chỉ được chạm khi ta duyệt qua nó từ một đầu mút, tổng ${\sum }_u\mathrm{deg}(u)=2E$, cộng $O(V)$ để đi qua mọi đỉnh.

Kết luận thực hành: mặc định dùng danh sách kề. Chỉ chuyển sang ma trận kề khi $V$ nhỏ và bài cần kiểm tra "có cạnh không" liên tục (vd Floyd–Warshall, đồ thị đầy đủ).

⚠️ Lỗi thường gặp

• Lệch chỉ số đỉnh (0-index vs 1-index): đề thường đánh số đỉnh $1..n$, nhưng vector lại từ $0$. Triệu chứng: lỗi truy cập ngoài mảng hoặc thiếu một đỉnh. Cách tránh: khai báo adj(n + 1) và luôn dùng chỉ số $1..n$, bỏ trống ô $0$.
• Quên thêm cạnh chiều ngược với đồ thị vô hướng: chỉ ghi adj[u].push_back(v) mà quên adj[v].push_back(u). Triệu chứng: DFS/BFS bỏ sót đỉnh, đếm thành phần liên thông sai. Ngược lại, với đồ thị có hướng lại không được thêm chiều ngược — đọc kỹ đề "một chiều" hay "hai chiều".
• Cạnh lặp (multi-edge) và khuyên (self-loop): nhiều đề cho phép hai đỉnh có nhiều cạnh, hoặc cạnh $u\to u$. Ma trận kề kiểu A[u][v]=1 sẽ mất thông tin số cạnh (gộp thành 1); nếu cần đếm, dùng A[u][v]++. Self-loop trong danh sách kề khiến adj[u] chứa chính $u$ — cẩn thận khi đếm bậc.
• Dùng ma trận kề khi $V$ quá lớn: khai báo int A[100005][100005] gây tràn bộ nhớ (MLE) ngay lập tức ($~4·{10}^{10}$ byte). Với $V>2000$ gần như luôn phải dùng danh sách kề.
• Tràn số với trọng số: trọng số cạnh tới ${10}^9$, đường đi qua nhiều cạnh có thể vượt int ($\approx 2.1·{10}^9$). Khi cộng dồn khoảng cách (Dijkstra, đường đi ngắn nhất) phải dùng long long, và đặt INF đủ lớn nhưng tránh tràn khi cộng (vd INF = 1e18).
• Đọc dữ liệu chậm: với $m$ tới $2·{10}^5$ cạnh, dùng cin không tắt đồng bộ có thể TLE. Thêm ios::sync_with_stdio(false); cin.tie(nullptr); (C++) hoặc sys.stdin (Python).

Biến thể / Mở rộng

• Lưu cạnh kèm chỉ số cạnh: khi cần đánh dấu cạnh đã đi (thuật toán Euler, cầu/khớp), lưu adj[u].push_back({v, edge_id}) thay vì chỉ đỉnh.
• Đồ thị ẩn (implicit graph): với bài lưới/mê cung, không cần dựng adj tường minh — đỉnh là ô $(i,j)$, hàng xóm tính trực tiếp bằng 4 hướng $(\pm 1,0),(0,\pm 1)$. Đây là dạng "biểu diễn ngầm" rất hay gặp.
• Danh sách cạnh (edge list): chỉ lưu mảng các bộ ba $(u,v,w)$, không nhóm theo đỉnh. Gọn cho các thuật toán quét mọi cạnh như Kruskal (cây khung nhỏ nhất) hay Bellman–Ford.
• Sau khi nắm biểu diễn, bước tiếp theo là các thuật toán duyệt DFS/BFS rồi đường đi ngắn nhất — chúng đều xây trên đúng cấu trúc danh sách kề ở trên.

Bài tập luyện

• Đếm Số Phòng (cntrooms) — (Nghiệp dư) Đồ thị ẩn trên lưới: mỗi ô sàn là một đỉnh, đếm thành phần liên thông bằng DFS/BFS — luyện cách biểu diễn đồ thị ngầm không cần adj.
• Kiểm Tra Chuyến Bay (flightrchk) — (Nghiệp dư) Dựng danh sách kề cho đồ thị có hướng rồi DFS kiểm tra khả năng đến được — luyện phân biệt cạnh một chiều với hai chiều.
• Chia Đội (buildteams) — (Nghiệp dư) Xây danh sách kề vô hướng rồi tô 2 màu (bipartite) bằng BFS — luyện duyệt hàng xóm trên đồ thị có thể nhiều thành phần.
• Đường Đi Ngắn Nhất I (shortroute1) — (Nghiệp dư) Cần danh sách kề có trọng số ($c$ tới ${10}^9$) + Dijkstra — luyện lưu cặp (đỉnh, trọng số) và dùng long long tránh tràn.
• Hầm Ngục Hogwarts (cheese) — (Trung cấp) BFS trên lưới lớn với hàng xóm tính trực tiếp — bài tổng hợp biểu diễn ngầm và duyệt theo tầng.