Triển khai (phần 1)
Bài học 5 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.
Chúng ta bắt đầu bằng việc tìm hàng xóm.
Thử thách
DễCũng như mọi phép duyệt, trước tiên ta cần tìm các đỉnh kề với từng đỉnh. (Nếu bạn đã học khóa học DFS, đây chính là hàm trợ giúp đó.)
Viết một hàm (function) tên là getNeighbors, nhận mảng edges dạng phẳng (các cặp đỉnh vô hướng) và một đỉnh node, rồi trả về danh sách đã sắp xếp gồm các đỉnh kề với node, không có phần tử trùng lặp.
Ví dụ, getNeighbors([0,1, 0,2, 1,2, 3,0], 0) trả về [1, 2, 3].
Tự làm thử
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, 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