Giao diện
Đồ 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(deg(V))$ - Phải duyệt list của i. |
| Duyệt kề i | $O(V)$ - Phải quét cả hàng. | $O(deg(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 \ll 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!