Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Thuật toán Prim, thuật toán đồ thị của Coddy.
Ta bắt đầu với cạnh có trọng số nhỏ nhất rời khỏi một đỉnh, nước đi đầu tiên của Prim.
Thử thách
DễNước đi đầu tiên của Prim là xem các cạnh nối với đỉnh bắt đầu. Hãy xây dựng hàm tra cứu đó.
Viết một hàm có tên minEdgeFrom, nhận mảng phẳng edges (các bộ ba [u, v, w, ...], vô hướng) và một đỉnh node, rồi trả về trọng số nhỏ nhất trong số các cạnh nối với node. Nếu node không có cạnh nào, hãy trả về -1.
Ví dụ, minEdgeFrom([0,1,5, 0,2,3, 1,2,1], 0) trả về 3.
Tự làm thử
#include <stdlib.h>
int minEdgeFrom(int* edges, int edges_size, int node) {
// Viết code ở đây
return -1;
}
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