Đồ Thị (Graph): Tổng Quan

Đồ thị là cấu trúc dữ liệu mô phỏng các mối quan hệ đôi một giữa các đối tượng.

V (Vertex): Đỉnh (còn gọi là Node).
E (Edge): Cạnh (đường nối giữa 2 đỉnh).

Biểu Diễn Đồ Thị

Có 2 cách phổ biến nhất để lưu trữ đồ thị trong máy tính.

Đặc Điểm	Adjacency Matrix (Ma Trận Kề)	Adjacency List (Danh Sách Kề)
Cấu Trúc	Mảng 2 chiều `A[V][V]`. `A[i][j] = 1` nếu có cạnh nối i-j.	Mảng các Vector `List<int> adj[V]`. `adj[i]` chứa các đỉnh kề với i.
Bộ Nhớ	$O (V^{2})$ - Tốn kém nếu đồ thị thưa.	$O (V + E)$ - Tiết kiệm.
Kiểm tra i-j?	$O (1)$ - Rất nhanh.	$O (d e g (V))$ - Phải duyệt list của i.
Duyệt kề i	$O (V)$ - Phải quét cả hàng.	$O (d e g (V))$ - Chỉ duyệt node kề.
Khi nào dùng?	Đồ thị dày (Dense Graph), $E \approx V^{2}$ .	Đồ thị thưa (Sparse Graph), $E ≪ V^{2}$ . Hầu hết các bài toán thực tế dùng cái này.

Ứng Dụng Thực Tế: Network Routing

Mạng Internet, Hệ thống đường bộ, và cả Penrift Tunnel đều hoạt động dựa trên lý thuyết đồ thị. Mỗi thiết bị là một Node, mỗi kết nối P2P là một Edge. Việc tìm đường đi nhanh nhất cho gói tin chính là bài toán Shortest Path!

📚 Các Thuật Toán

Duyệt Đồ Thị

BFS & DFS - Hai kỹ thuật duyệt cơ bản nhất

Đường Đi Ngắn Nhất (Shortest Path)

Dijkstra - Single-source, non-negative weights. $O (E \log V)$
Bellman-Ford - Single-source, negative weights OK. Forex arbitrage detection. $O (V \times E)$
Floyd-Warshall - All-pairs shortest path. Connectivity matrix. $O (V^{3})$

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

Scenario	Algorithm
Non-negative, single source	Dijkstra
Negative weights possible	Bellman-Ford
Need all pairs distances	Floyd-Warshall
Detect negative cycle	Bellman-Ford hoặc Floyd-Warshall

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. Network infrastructure, clustering.

Structural Algorithms

Topological Sort - Task scheduling, build dependencies (Kahn's Algorithm). $O (V + E)$
Disjoint Set Union (DSU) - Connected components, Kruskal's MST. $O (α (N)) \approx O (1)$

Tree Queries

LCA - Binary Lifting - Lowest Common Ancestor với kỹ thuật "Nhảy cóc theo lũy thừa 2". $O (\log N)$ query sau $O (N \log N)$ tiền xử lý.

Network Flow (Luồng Mạng)

Max Flow & Edmonds-Karp - Maximum throughput, Bipartite Matching, Min-Cut. $O (V E^{2})$

💡 Khi nào nghĩ đến Max Flow?

Scenario	Ứng dụng
Tối ưu throughput qua mạng lưới	Logistics, Network bandwidth
Ghép đôi 2 tập hợp (Bipartite Matching)	Job assignment, Dating apps
Tìm điểm nghẽn (Bottleneck)	Min-Cut = điểm yếu nhất của hệ thống

Đồ Thị (Graph): Tổng Quan ​

Biểu Diễn Đồ Thị ​

Ứng Dụng Thực Tế: Network Routing ​

📚 Các Thuật Toán ​

Duyệt Đồ Thị ​

Đường Đi Ngắn Nhất (Shortest Path) ​

Cây Khung Nhỏ Nhất (Minimum Spanning Tree) ​

Structural Algorithms ​

Tree Queries ​

Network Flow (Luồng Mạng) ​