Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Tìm kiếm theo chiều rộng, thuật toán đồ thị của Coddy.
Bây giờ, chúng ta duyệt đồ thị theo từng lớp bằng hàng đợi.
Thử thách
Trung bìnhBây giờ, hãy hoàn thành toàn bộ quá trình duyệt.
Viết một hàm tên là bfs, nhận n, mảng edges dạng phẳng (đồ thị vô hướng) và đỉnh start, rồi trả về thứ tự BFS thăm các đỉnh bắt đầu từ start.
Tạo danh sách kề (các đỉnh lân cận được sắp xếp theo thứ tự tăng dần), rồi dùng hàng đợi: đánh dấu và thêm đỉnh bắt đầu vào hàng đợi, sau đó liên tục lấy một đỉnh ra khỏi hàng đợi, ghi lại đỉnh đó và thêm các đỉnh lân cận chưa được thăm vào hàng đợi. Chỉ những đỉnh có thể đi đến từ start mới được thăm.
Tự làm thử
#include <stdlib.h>
int* bfs(int n, int* edges, int edges_size, int start, 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 Tìm kiếm theo chiều rộng, 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 thời gian và không gianTự luyện tập: Trình biên dịch C online