đã đăng vào 1 tháng 4 năm 2025, 12:33 a.m.
🌐 Cheatsheet Chi Tiết: Lý Thuyết Đồ Thị & Cây (Graph & Tree Theory)
🧠 Khái Niệm Cơ Bản
| Thuật ngữ |
Mô tả |
| Đỉnh (vertex) |
Một nút trong đồ thị hoặc cây |
| Cạnh (edge) |
Kết nối giữa hai đỉnh |
| Bậc (degree) |
Số cạnh nối vào một đỉnh (in/out degree với đồ thị có hướng) |
| Đường đi (path) |
Chuỗi đỉnh nối nhau bằng cạnh |
| Chu trình (cycle) |
Đường đi bắt đầu và kết thúc tại cùng một đỉnh |
| Cây (tree) |
Đồ thị vô hướng, liên thông, không chu trình |
| DAG |
Đồ thị có hướng không có chu trình (Directed Acyclic Graph) |
📌 Ứng Dụng Đồ Thị & Cây
- Tìm đường đi ngắn nhất: giao thông, mạng máy tính (Dijkstra, BFS)
- Tối ưu mạng lưới: xây dựng cây khung nhỏ nhất (Kruskal, Prim)
- Phân tích cấu trúc: SCC, Biconnected, Cầu/Khớp (Tarjan, Kosaraju)
- Quản lý phân cấp: tổ chức, biểu đồ thừa kế → dùng cây
- Truy vấn tổ tiên, phân đoạn cây: LCA, HLD, Euler Tour
🎯 Biểu Diễn Đồ Thị
Danh sách kề (Adjacency List) — Thường dùng
vector<vector<int>> adj(n + 1);
adj[u].push_back(v);
Ma trận kề (Adjacency Matrix) — Chỉ dùng khi đồ thị dày
vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
g[u][v] = 1;
DSU — Dùng trong Kruskal, Union-Find
vector<int> parent(n + 1);
iota(parent.begin(), parent.end(), 0);
int find(int u) {
return u == parent[u] ? u : parent[u] = find(parent[u]);
}
void unite(int u, int v) {
parent[find(u)] = find(v);
}
🔄 Duyệt Đồ Thị
DFS (Depth-First Search)
void dfs(int u) {
visited[u] = true;
for (int v : adj[u])
if (!visited[v]) dfs(v);
}
BFS (Breadth-First Search)
void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u])
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
🌲 DFS Trên Cây — Truy Vết, Kích Thước, Chiều Sâu
vector<int> parent(n + 1), depth(n + 1), size(n + 1);
void dfs_tree(int u, int p) {
parent[u] = p;
size[u] = 1;
depth[u] = depth[p] + 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs_tree(v, u);
size[u] += size[v];
}
}
📉 Tìm Tổ Tiên Chung Gần Nhất (LCA - Binary Lifting)
const int LOG = 20;
int up[MAXN][LOG], tin[MAXN], tout[MAXN], timer;
void dfs_lca(int u, int p) {
tin[u] = ++timer;
up[u][0] = p;
for (int i = 1; i < LOG; ++i)
up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : adj[u])
if (v != p) dfs_lca(v, u);
tout[u] = ++timer;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = LOG - 1; i >= 0; --i)
if (!is_ancestor(up[u][i], v))
u = up[u][i];
return up[u][0];
}
📚 Khi Nào Dùng Kỹ Thuật Nào?
| Nhu cầu |
Thuật toán / Kỹ thuật |
| Duyệt đồ thị |
DFS / BFS |
| Đếm thành phần liên thông |
DFS |
| Tìm đường ngắn nhất |
BFS (đơn vị), Dijkstra |
| Tìm tổ tiên chung (LCA) |
Binary Lifting / RMQ |
| Cây khung nhỏ nhất |
Kruskal / Prim |
| Tìm chu trình |
DFS + back edge |
| Phân tích cấu trúc |
Tarjan, SCC, Bridge, AP |
| Truy vấn trên đường đi hoặc cây con |
Euler Tour + Segment Tree |
| Cập nhật động trên cây |
HLD, Link Cut Tree (nâng cao) |
📈 Độ Phức Tạp Tổng Hợp
| Thuật toán |
Thời gian |
Không gian |
| DFS / BFS |
O(V + E) |
O(V + E) |
| Kruskal (với DSU) |
O(E log E) |
O(V) |
| Dijkstra (PQ) |
O((V + E) log V) |
O(V + E) |
| Tarjan (SCC, cầu, khớp) |
O(V + E) |
O(V + E) |
| LCA (binary lifting) |
O(log N) |
O(N log N) |
📚 Tham Khảo
- CP-Algorithms - Graph Theory
- CSES Graph & Tree Algorithms
- AtCoder Educational DP Contest (Tree DP)
- VNOI / SPOJ / Codeforces Tag "graphs", "trees"
Nhận xét