Lập trình C++ nâng cao - Cấu trúc dữ liệu và Giải thuật | NenTang.vn |
Sản phẩm của Nền tảng | NenTang.vn - Hành trang tới Tương lai |
Lập trình C++ nâng cao - Cấu trúc dữ liệu và Giải thuật | NenTang.vn |
Chương 1-Bài 22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất |
||
Tác giả: Dương Nguyễn Phú Cường | Ngày đăng: Hồi xưa đó | Lượt xem: 377 |
Mô tả
Bước 1: lập bảng, liệt kê tăng dần theo trọng số của các cạnh.
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ợp 6-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ợp 4-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ợp 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ợp 1-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. 2-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. 3-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. 5-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ợp CÂY BAO TRÙM THU ĐƯỢC, Hình 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:
|
Sản phẩm của Nền tảng | NenTang.vn - Hành trang tới Tương lai |