Triển khai phần 2
Bài học 6 trên 9 trong khóa học Sắp xếp tô pô trong đồ thị của Coddy.
Bây giờ, ta liên tục loại bỏ các đỉnh có bậc vào bằng 0 để tạo thứ tự.
Thử thách
Trung bìnhBây giờ, hãy xây dựng thứ tự đầy đủ.
Viết một hàm (function) tên là topologicalSort, nhận n và mảng edges chứa các cạnh được biểu diễn bằng dãy phẳng (u -> v), rồi trả về một thứ tự tô pô của các đỉnh.
Dùng thuật toán Kahn: tính bậc vào, sau đó liên tục chọn đỉnh nhỏ nhất có bậc vào bằng 0, thêm đỉnh đó vào kết quả và giảm bậc vào của các đỉnh kề đi ra. Đầu vào của thử thách này không có chu trình.
Mỗi bước chọn đỉnh nhỏ nhất hiện có sẽ giúp đáp án là duy nhất.
Tự làm thử
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Viết code ở đây
*returnSize = 0;
return edges;
}
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 Sắp xếp tô pô trong đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai phần 1Triển khai phần 2
Độ phức tạp về thời gian và bộ nhớTự luyện tập: Trình biên dịch C online