Có những cách nào để biểu diễn đồ thị?
Có những cách nào để biểu diễn đồ thị?
| Cách | Bộ nhớ | Kiểm tra cạnh (u,v) | Duyệt láng giềng của u | Phù hợp |
|---|---|---|---|---|
Ma trận kề A[u][v] |
O(V²) | O(1) | O(V) | Đồ thị dày, V nhỏ, Floyd–Warshall |
| Danh sách kề | O(V + E) | O(deg(u)) | O(deg(u)) | Đồ thị thưa (hầu hết thực tế) |
| Danh sách cạnh | O(E) | O(E) | O(E) | Kruskal, Bellman–Ford |
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.