Giới thiệu cây khung đồ thị
Cây khung (hay cây bao trùm) của một đồ thị là một cây con của đồ thị đó, chứa tất cả các đỉnh của đồ thị nhưng không có chu trình. Cây khung có những đặc điểm chính sau:
- Bao gồm tất cả các đỉnh: Cây khung phải chứa tất cả các đỉnh của đồ thị gốc.
- Không có chu trình: Cây khung không chứa chu trình (các vòng khép kín).
- Đồ thị liên thông: Nếu đồ thị ban đầu là liên thông, cây khung của nó cũng phải là liên thông.
Cây khung nhỏ nhất (Minimum Spanning Tree - MST):
Khi nói về cây khung, chúng ta thường quan tâm đến cây khung nhỏ nhất (MST) của một đồ thị trọng số, tức là cây khung mà tổng trọng số của các cạnh là nhỏ nhất. Có một số thuật toán nổi tiếng để tìm MST, bao gồm:
- Thuật toán Kruskal: Tìm MST bằng cách chọn cạnh có trọng số nhỏ nhất và thêm nó vào cây khung sao cho không tạo ra chu trình, cho đến khi tất cả các đỉnh đều được kết nối.
- Thuật toán Prim: Bắt đầu từ một đỉnh bất kỳ, thêm cạnh có trọng số nhỏ nhất kết nối đỉnh đó với một đỉnh chưa được thăm, và tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.
Lợi ích và ứng dụng:
Cây khung và cây khung nhỏ nhất có nhiều ứng dụng thực tế trong các lĩnh vực như:
- Mạng lưới điện: Tìm cách kết nối tất cả các trạm điện với chi phí thấp nhất.
- Thiết kế mạng: Kết nối các máy tính trong một mạng sao cho chi phí xây dựng mạng là thấp nhất.
- Tối ưu hóa giao thông: Tìm cách kết nối các thành phố bằng hệ thống đường bộ hoặc đường sắt với chi phí xây dựng thấp nhất.
| Thuật toán | Prim | Kruskal |
|---|---|---|
| Cách tiếp cận | Thuật toán tham lam, xây dựng MST từ một đỉnh ban đầu và mở rộng bằng cách thêm cạnh ngắn nhất kết nối với cây khung hiện tại. | Thuật toán tham lam, bắt đầu bằng các cạnh nhỏ nhất và thêm vào nếu nó không tạo chu trình (sử dụng cấu trúc dữ liệu Disjoint Set). |
| Độ phức tạp thời gian (Big O) |
O(E + V log V) với cấu trúc dữ liệu Fibonacci heap O(V²) với ma trận kề O(E log V) với hàng đợi ưu tiên và danh sách kề |
O(E log V) với cấu trúc dữ liệu Union-Find |
| Độ phức tạp không gian | O(V) để lưu trữ mảng key, parent và inMST | O(V + E) để lưu trữ danh sách cạnh và cấu trúc Disjoint Set |
| Độ phức tạp bộ nhớ
|
O(V) với danh sách kề O(V²) với ma trận kề |
O(V + E)
|
| Đầu vào | Đồ thị liên thông, không có hướng, trọng số không âm | Đồ thị không có hướng, trọng số không âm, không yêu cầu liên thông nhưng chỉ các thành phần liên thông sẽ được xử lý |
| Cấu trúc dữ liệu | Hàng đợi ưu tiên, mảng | Danh sách cạnh, cấu trúc Disjoint Set (Union-Find) |
| Ưu điểm |
Tốt cho đồ thị dày đặc (dense graph) do độ phức tạp thấp với ma trận kề Thời gian thực thi nhanh với đồ thị lớn và liên thông |
Tốt cho đồ thị thưa (sparse graph) do việc xử lý các cạnh ít hơn Dễ triển khai và hiểu |
| Nhược điểm | Không hiệu quả cho đồ thị thưa (sparse graph) nếu sử dụng ma trận kề | Cần sắp xếp tất cả các cạnh trước khi xây dựng MST, có thể tốn thời gian với số lượng cạnh lớn |