Đồ thị — Tổng quan

Mạng xã hội, hệ thống định tuyến Internet, bản đồ giao thông, dependency graph trong CI/CD — tất cả đều là đồ thị. Khi bạn gõ một URL, gói tin phải tìm đường qua hàng chục router; khi Kubernetes schedule một Pod, nó phải giải bài toán ràng buộc trên đồ thị phụ thuộc.

Nắm vững lý thuyết đồ thị không chỉ giúp bạn giải bài competitive programming, mà quan trọng hơn là giúp bạn thiết kế hệ thống có khả năng mở rộng và debug hiệu quả khi production gặp sự cố.

Biểu diễn đồ thị

Mọi thuật toán đồ thị bắt đầu từ cách bạn lưu trữ nó trong bộ nhớ. Hai cách phổ biến nhất — mỗi cách có trade-off rõ ràng.

Tiêu chí	Ma trận kề (Adjacency Matrix)	Danh sách kề (Adjacency List)
Cấu trúc	Mảng 2D A[V][V]. A[i][j] = 1 nếu có cạnh i → j	Mảng vector adj[V]. adj[i] chứa các đỉnh kề với i
Bộ nhớ	$O(V^2)$ — tốn kém khi đồ thị thưa	$O(V+E)$ — tiết kiệm
Kiểm tra cạnh i-j	$O(1)$	$O(\mathrm{deg}(i))$
Duyệt đỉnh kề i	$O(V)$ — quét cả hàng	$O(\mathrm{deg}(i))$ — chỉ duyệt đỉnh kề
Phù hợp	Đồ thị dày ($E\approx V^2$), Floyd-Warshall	Đồ thị thưa ($E\ll V^2$) — hầu hết production

Quy tắc chọn nhanh

Nếu $E<V^2/10$ → danh sách kề. Nếu cần kiểm tra cạnh $O(1)$ liên tục hoặc V nhỏ (≤ 1000) → ma trận kề.

Lộ trình học

Thứ tự khuyến nghị để xây dựng nền tảng vững chắc, từ duyệt cơ bản đến luồng mạng.

BFS & DFS → Dijkstra → Bellman-Ford → Floyd-Warshall
    ↓                                        ↓
Topological Sort → DSU → MST       LCA · Binary Lifting
                                             ↓
                                    Max Flow · Edmonds-Karp

Nội dung

Duyệt đồ thị

• BFS & DFS — Hai kỹ thuật nền tảng: duyệt theo chiều rộng và chiều sâu

Đường đi ngắn nhất (Shortest Path)

Thuật toán	Loại	Trọng số âm	Độ phức tạp	Khi nào dùng
Dijkstra	Single-source	❌	$O((V+E)\log V)$	GPS, routing, game pathfinding
Bellman-Ford	Single-source	✅	$O(V\times E)$	Phát hiện chu trình âm, forex arbitrage
Floyd-Warshall	All-pairs	✅	$O(V^3)$	Routing table, connectivity matrix

Chọn thuật toán nào?

Bài toán	Chọn
Trọng số ≥ 0, một nguồn	Dijkstra
Có cạnh trọng số âm	Bellman-Ford
Cần khoảng cách mọi cặp đỉnh	Floyd-Warshall
Phát hiện chu trình âm	Bellman-Ford hoặc Floyd-Warshall
Đồ thị thưa, all-pairs, trọng số âm	Johnson's (Bellman-Ford + Dijkstra)

Cây khung nhỏ nhất (Minimum Spanning Tree)

• MST — Prim & Kruskal — Kết nối tất cả đỉnh với chi phí tối thiểu. Ứng dụng: thiết kế mạng, clustering.

Thuật toán cấu trúc

• Topological Sort — Sắp xếp topo cho DAG: task scheduling, build dependencies. $O(V+E)$
• Disjoint Set Union (DSU) — Quản lý thành phần liên thông, hỗ trợ Kruskal. $O(\alpha (N))\approx O(1)$

Truy vấn trên cây

• LCA — Binary Lifting — Lowest Common Ancestor bằng kỹ thuật nhảy lũy thừa 2. Query $O(\log N)$ sau tiền xử lý $O(N\log N)$.

Luồng mạng (Network Flow)

• Max Flow — Edmonds-Karp — Throughput tối đa, bipartite matching, min-cut. $O(V{E}^2)$

🧠 Quiz

Câu 1: Để tìm đường ngắn nhất từ một đỉnh đến TẤT CẢ đỉnh khác trong đồ thị có trọng số dương, dùng thuật toán nào?

• [ ] A) BFS (Breadth-First Search)
• [x] B) Dijkstra's Algorithm
• [ ] C) DFS (Depth-First Search)
• [ ] D) Kruskal's Algorithm

💡 Giải thích: Dijkstra giải Single-Source Shortest Path cho đồ thị trọng số dương trong O((V+E) log V) với priority queue. BFS chỉ đúng cho đồ thị unweighted. DFS không tìm đường ngắn nhất. Kruskal tìm MST, không phải shortest path.

Câu 2: Topological Sort áp dụng cho loại đồ thị nào?

• [ ] A) Đồ thị vô hướng có chu trình
• [ ] B) Đồ thị có trọng số âm
• [x] C) DAG — Đồ thị có hướng không có chu trình (Directed Acyclic Graph)
• [ ] D) Bất kỳ đồ thị nào

💡 Giải thích: Topological ordering chỉ tồn tại cho DAG — nếu có chu trình thì không thể sắp xếp sao cho mọi cạnh u→v đều có u đứng trước v. Ứng dụng: build system (Makefile), course prerequisites, task scheduling.

Câu 3: Disjoint Set Union (DSU) hỗ trợ hai thao tác chính nào?

• [ ] A) Insert và Delete
• [ ] B) Push và Pop
• [x] C) Find (tìm đại diện tập hợp) và Union (gộp hai tập hợp)
• [ ] D) Search và Sort

💡 Giải thích: DSU (Union-Find) có Find O(α(n)) ≈ O(1) (amortized) và Union O(α(n)). Với path compression + union by rank, α(n) là inverse Ackermann — gần như hằng số. Dùng trong Kruskal's MST, connected components, và xử lý equivalence relations.

📚 Bài liên quan

Liên kết

• Sorting — Tổng quan — Thuật toán sắp xếp cơ bản và nâng cao
• Dynamic Programming — Quy hoạch động — nền tảng cho Floyd-Warshall

Từ khóa glossary: đồ thị, graph, adjacency list, adjacency matrix, shortest path, MST, network flow

Tìm kiếm liên quan: thuật toán đồ thị, lý thuyết đồ thị, graph algorithms, duyệt đồ thị