Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu DFS – Depth First Search
Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Giải Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu - Kết nối tri thức
Hoạt động 1 trang 65 Chuyên đề Tin học 12: Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Lời giải:
Ý tưởng chính của DFS:
DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, đánh dấu nó là đã thăm, sau đó tiếp tục đi sâu vào các đỉnh kề chưa thăm cho đến khi không thể đi tiếp được nữa. Khi không thể đi tiếp, thuật toán quay lui về các đỉnh trước đó để tiếp tục tìm kiếm các đường đi mới.
Lời giải bài tập Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu hay, ngắn gọn khác: