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 sâu, thuật toán đồ thị của Coddy.
Bây giờ, chúng ta duyệt toàn bộ đồ thị bằng một ngăn xếp.
Thử thách
Trung bìnhBây giờ, hãy xây dựng thuật toán duyệt hoàn chỉnh.
Viết một hàm (function) có tên dfs, nhận n, mảng edges phẳng (biểu diễn các cạnh vô hướng) và đỉnh start, rồi trả về thứ tự DFS thăm các đỉnh, bắt đầu từ start.
Trước tiên, hãy xây dựng danh sách kề (sắp xếp các đỉnh kề của mỗi đỉnh theo thứ tự tăng dần). Sau đó, chạy DFS lặp bằng ngăn xếp. Chỉ các đỉnh có thể đi đến từ start mới được thăm.
Để thăm các đỉnh kề theo thứ tự tăng dần, hãy đẩy chúng vào ngăn xếp từ lớn nhất đến nhỏ nhất.
Tự làm thử
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Viết code vào đâ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