Hiểu sự khác biệt giữa Prim và Kruskal để tìm Minimum Spanning Tree (MST).
Kruskal's algorithm cho MST
- Đồ thị liên thông vô hướng → spanning tree là cây con kết nối mọi đỉnh.
- Một đồ thị có nhiều spanning tree.
- MST: spanning tree có trọng số nhỏ nhất hoặc bằng mọi spanning tree khác.
- Trọng số spanning tree = tổng trọng số cạnh.
- MST có thể xây từ đỉnh có trọng số nhỏ nhất.
- Mỗi đỉnh duyệt một lần.
- Nhanh trên đồ thị thưa (sparse).
- Độ phức tạp O(E log V).
- Làm việc được với disconnected components.
Các bước Kruskal
- Sắp xếp cạnh theo trọng số tăng dần.
- Chọn cạnh nhỏ nhất.
- Kiểm tra có tạo chu trình với spanning tree hiện tại không.
- Không tạo chu trình → thêm cạnh.
- Ngược lại → bỏ qua.
- Lặp lại cho đến khi spanning tree có V-1 cạnh.
Prim's algorithm MST
- Tương tự Kruskal: greedy algorithm.
- Bắt đầu spanning tree rỗng. Duy trì 2 tập đỉnh.
- Tập 1: đỉnh đã trong MST. Tập 2: đỉnh chưa trong MST.
- Mỗi bước: xét tất cả cạnh nối 2 tập, chọn cạnh trọng số nhỏ nhất.
- Di chuyển đến đỉnh kia của cạnh đó, thêm vào tập MST.
- MST có thể xây từ bất kỳ đỉnh nào.
- Đỉnh có thể duyệt nhiều lần để lấy khoảng cách nhỏ nhất.
- Độ phức tạp O(V^2), cải tiến O(E + log V) với Fibonacci heap.
- Nhanh trên đồ thị đậm (dense).
- Cho connected components, chỉ làm việc với connected graph.
Các bước Prim
- Tạo mstSet theo dõi đỉnh đã trong MST.
- Gán key value cho mọi đỉnh (INFINITE).
- Key = 0 cho đỉnh đầu tiên để chọn trước.
- Khi mstSet chưa chứa hết đỉnh:
- Chọn đỉnh 'u' không trong mstSet, key nhỏ nhất.
- Thêm 'u' vào mstSet.
- Cập nhật key các đỉnh kề 'u': nếu trọng số u-v < key[v] → key[v] = weight(u,v).