Chương 1-Bài 22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất
legacy-admin-baitap-1
2 thg 2, 2025
1.779 lượt xem
1 giờ 42 phút
Mô tả
Giống như Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất nhưng không phụ thuộc vào điểm bắt đầu.
Hình 1, đồ thị như sau:
cay_khung_nho_nhat_kruskal_huong_dan_do_thi_1
Bước 1: lập bảng, liệt kê tăng dần theo trọng số của các cạnh.
Đỉnh U
Đỉnh V
Trọng số
1
4
1
6
7
1
4
6
2
1
2
3
1
6
3
3
4
3
2
3
4
3
7
5
5
6
5
2
6
6
4
5
6
3
5
7
Bước 2: dựa vào thứ tự bảng trên để đánh giá cạnh đó có thuộc cây khung tối tiểu hay không. Một cạnh thõa điều kiện khi nó không góp phần tạo thành một chu trình với tất cả các cạnh đã tìm được.
1-4-1: Ta nhận thấy cạnh 1-4 không tạo ra một chu trình nào. Vì vậy, thêm 1-4 vào tập hợpcay_khung_nho_nhat_kruskal_huong_dan_26-7-1: Ta nhận thấy cạnh 6-7 không tạo ra một chu trình nào. Vì vậy, thêm 6-7 vào tập hợpcay_khung_nho_nhat_kruskal_huong_dan_34-6-2: Ta nhận thấy cạnh 4-6 không tạo ra một chu trình nào. Vì vậy, thêm 4-6 vào tập hợpcay_khung_nho_nhat_kruskal_huong_dan_4 1-2-3: Ta nhận thấy cạnh 1-2 không tạo ra một chu trình nào. Vì vậy, thêm 1-2 vào tập hợpcay_khung_nho_nhat_kruskal_huong_dan_51-6-3: Ta nhận thấy cạnh 1-6 tạo ra một chu trình. Không thêm vào tập hợp.cay_khung_nho_nhat_kruskal_huong_dan_62-3-4: Ta nhận thấy cạnh 2-3 tạo ra một chu trình. Không thêm vào tập hợp.cay_khung_nho_nhat_kruskal_huong_dan_73-7-5: Ta nhận thấy cạnh 3-7 tạo ra một chu trình. Không thêm vào tập hợp.cay_khung_nho_nhat_kruskal_huong_dan_85-6-5: Ta nhận thấy cạnh 5-6 không tạo ra một chu trình nào. Vì vậy, thêm 5-6 vào tập hợpcay_khung_nho_nhat_kruskal_huong_dan_9CÂY BAO TRÙM THU ĐƯỢC, Hình 10:cay_khung_nho_nhat_kruskal_huong_dan_10
Cài đặt
– Bước 1, khai báo các biến, ta sẽ không sử dụng ma trận kề để lưu đồ thị, mà sẽ sử dụng danh sách các cạnh đã khai báo để lưu từng cạnh, vì vậy khi nhập dữ liệu vào, ta cần gán dữ liệu vào danh sách các cạnh:
Các hàm cần thiết:
Hàm find(v): tìm nút gốc của đỉnh v.
Hàm Union(u, v): hàm nối 2 đỉnh lại với nhau.
Hàm sort(): dùng để sắp xếp các cạnh tăng dần theo trọng số