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 sâu, thuật toán đồ thị của Coddy.
Chúng ta sẽ xây dựng DFS bắt đầu từ tra cứu danh sách kề.
Thử thách
DễTrước khi duyệt đồ thị, ta cần biết các đỉnh kề với từng đỉnh. Hãy tạo bảng tra cứu này từ danh sách cạnh phẳng.
Viết một hàm có tên getNeighbors, nhận mảng edges gồm các cặp phẳng [u0, v0, u1, v1, ...] (đồ thị vô hướng) và một đỉnh node, rồi trả về danh sách đã sắp xếp 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 sâu, 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