Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Thuật toán Kruskal: thuật toán trên đồ thị của Coddy.
Giờ hãy thêm cạnh an toàn có trọng số nhỏ nhất cho đến khi hoàn thành cây khung nhỏ nhất.
Thử thách
Trung bìnhBây giờ, hãy xây dựng cây khung nhỏ nhất.
Viết một hàm có tên kruskal, nhận n và mảng phẳng edges (gồm các bộ ba, biểu diễn cạnh vô hướng) của một đồ thị liên thông, rồi trả về tổng trọng số của cây khung nhỏ nhất.
Liên tục chọn cạnh chưa dùng có trọng số thấp nhất. Nếu hai đầu mút của cạnh thuộc hai tập hợp khác nhau, hãy hợp nhất hai tập hợp đó và cộng trọng số của cạnh vào tổng. Nếu không, hãy bỏ qua cạnh đó.
Dùng lại ý tưởng union-find trong bài học trước.
Tự làm thử
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Viết code ở đây
return 0;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Thuật toán Kruskal: thuật toán trên đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online