Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Thuật toán Prim, thuật toán đồ thị của Coddy.
Bây giờ, hãy phát triển cây, luôn thêm cạnh bắc qua có chi phí thấp nhất.
Thử thách
Trung bìnhGiờ hãy phát triển toàn bộ cây.
Viết một hàm (function) tên là prim, nhận n và mảng edges dạng phẳng (các bộ ba, 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, bắt đầu tạo cây từ đỉnh 0.
Giữ một cờ inTree cho mỗi đỉnh. Mỗi vòng, tìm cạnh có trọng số nhỏ nhất mà chỉ có đúng một đầu mút nằm trong cây, cộng trọng số của cạnh đó, rồi thêm đầu mút còn lại vào cây.
Tự làm thử
#include <stdlib.h>
int prim(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 Prim, thuật toá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 về thời gian và không gianTự luyện tập: Trình biên dịch C online