Cây bao trùm tối thiểu DSA
Bài toán cây bao trùm tối thiểu
Cây kéo dài tối thiểu (MST) là tập hợp các cạnh cần thiết để kết nối tất cả các đỉnh trong đồ thị vô hướng, với tổng trọng lượng cạnh tối thiểu.
Hoạt ảnh ở trên chạy thuật toán của Prim để tìm MST. Một cách khác để tìm MST, cũng có tác dụng với các đồ thị không liên thông, là chạy thuật toán Kruskal .
Nó được gọi là Cây kéo dài tối thiểu, bởi vì nó là một biểu đồ được kết nối, không tuần hoàn, vô hướng, là định nghĩa của cấu trúc dữ liệu cây.
Trong thế giới thực, việc tìm Cây kéo dài tối thiểu có thể giúp chúng ta tìm ra cách hiệu quả nhất để kết nối các ngôi nhà với internet hoặc với lưới điện hoặc có thể giúp chúng ta tìm ra con đường nhanh nhất để giao các gói hàng.
Một thử nghiệm tư duy MST
Hãy tưởng tượng rằng các vòng tròn trong hình ảnh động trên là những ngôi làng không có điện và bạn muốn kết nối chúng với lưới điện. Sau khi thôn nào có điện, dây cáp điện phải được trải từ thôn đó sang làng khác. Các ngôi làng có thể được kết nối bằng nhiều cách khác nhau, mỗi tuyến đường có chi phí khác nhau.
Dây cáp điện rất đắt tiền, việc đào mương để đặt dây cáp hoặc kéo căng dây cáp trên không cũng rất tốn kém. Địa hình chắc chắn có thể là một thách thức và có thể sẽ có chi phí bảo trì trong tương lai khác nhau tùy thuộc vào vị trí kết thúc của cáp.
Tất cả các chi phí tuyến đường này có thể được tính vào trọng số cạnh trong biểu đồ. Mỗi đỉnh tượng trưng cho một ngôi làng và mỗi cạnh tượng trưng cho một tuyến đường cáp điện có thể nối giữa hai ngôi làng.
Sau khi tạo xong biểu đồ như vậy, có thể tìm thấy Cây kéo dài tối thiểu (MST) và đó sẽ là cách hiệu quả nhất để kết nối những ngôi làng này với lưới điện.
Và đây thực sự là mục đích của thuật toán MST đầu tiên (thuật toán Borůvka) vào năm 1926: Để tìm ra cách tốt nhất để kết nối khu vực lịch sử Moravia, thuộc Cộng hòa Séc, với lưới điện.
Thuật toán MST
Hai trang tiếp theo trong hướng dẫn này giải thích hai thuật toán tìm Cây khung tối thiểu trong đồ thị: Thuật toán Prim và thuật toán Kruskal .
Prim's algorithm | Kruskal's algorithm | |
---|---|---|
Can it find MSTs (a Minimum Spanning Forest) in an unconnected graph? | No | Yes |
How does it start? | The MST grows from a randomly chosen vertex. | The first edge in the MST is the edge with lowest edge weight. |
What time complexity does it have? | \(O(V^2)\), or \( O( E \cdot \log{V}) \) (Optimized) | \( O( E \cdot \log{E} ) \) |