Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(1):
.jpg)
Trả lời:
Đáp án đúng: D
Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu từ đỉnh 1, duyệt theo chiều sâu.
1. Bắt đầu từ đỉnh 1.
2. Duyệt đỉnh kề chưa được thăm của 1, ví dụ đỉnh 2.
3. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 7.
4. Duyệt đỉnh kề chưa được thăm của 7, ví dụ đỉnh 4.
5. Duyệt đỉnh kề chưa được thăm của 4, ví dụ đỉnh 5.
6. Duyệt đỉnh kề chưa được thăm của 5, ví dụ đỉnh 10.
7. Quay lui lại 4, không còn đỉnh kề chưa thăm. Quay lui lại 7, không còn đỉnh kề chưa thăm. Quay lui lại 2.
8. Duyệt đỉnh kề chưa được thăm của 2, ví dụ đỉnh 3.
9. Duyệt đỉnh kề chưa được thăm của 3, ví dụ đỉnh 6.
10. Duyệt đỉnh kề chưa được thăm của 6, ví dụ đỉnh 9.
11. Duyệt đỉnh kề chưa được thăm của 9, ví dụ đỉnh 8.
Vậy, thứ tự duyệt các đỉnh là: 1, 2, 7, 4, 5, 10, 3, 6, 9, 8.
Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!
30 câu hỏi 60 phút
