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

Wiki › Cấu trúc dữ liệu

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

huunguyen · Last updated 28, Tháng 3, 2026, 22:45

Đồ thị $G = (V, E)$ gồm tập đỉnh $V$ và tập cạnh $E$ . Có hai cách biểu diễn chính trong lập trình thi đấu.

1. Danh sách kề (Adjacency List)

Mỗi đỉnh lưu danh sách các đỉnh kề với nó.

Ưu điểm: Tiết kiệm bộ nhớ $O (V + E)$ , duyệt cạnh nhanh.
Nhược điểm: Kiểm tra cạnh $(u, v)$ tồn tại mất $O (\deg (u))$ .

C++

int n, m;
vector<vector<int>> adj(n);

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

// Có trọng số
vector<vector<pair<int,int>>> wadj(n);
wadj[u].push_back({v, w});

Python

from collections import defaultdict
adj = defaultdict(list)
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

# Có trọng số
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

2. Ma trận kề (Adjacency Matrix)

Mảng 2D adj[u][v] = trọng số nếu có cạnh, 0 nếu không.

Ưu điểm: Kiểm tra cạnh tồn tại $O (1)$ .
Nhược điểm: Tốn bộ nhớ $O (V^{2})$ — chỉ dùng khi $N \leq 1000$ .

int adj[1005][1005] = {};
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u][v] = w;
    adj[v][u] = w;
}

So sánh

	Danh sách kề	Ma trận kề
Bộ nhớ	$O (V + E)$	$O (V^{2})$
Kiểm tra cạnh $(u, v)$	$O (\deg (u))$	$O (1)$
Duyệt hàng xóm $u$	$O (\deg (u))$	$O (V)$
Phù hợp khi	Đồ thị thưa	Đồ thị dày hoặc $V$ nhỏ

Các thuật ngữ quan trọng

Thuật ngữ	Ý nghĩa
Đồ thị có hướng	Cạnh có chiều: $u \to v \neq v \to u$
Đồ thị vô hướng	Cạnh không có chiều: $u - v$
Bậc (degree)	Số cạnh nối với một đỉnh
Thành phần liên thông	Nhóm đỉnh có thể đi tới nhau
Cây (Tree)	Đồ thị liên thông không có chu trình, $E = V - 1$

Đọc đầu vào mẫu

int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);  // 1-indexed
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});
}

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

Bình luận

Không có bình luận tại thời điểm này.