Với đồ thị Hình 14.3 thì thứ tự các đỉnh đã duyệt theo chiều sâu, bắt đầu từ đỉnh 0
Với đồ thị Hình 14.3 thì thứ tự các đỉnh đã duyệt theo chiều sâu, bắt đầu từ đỉnh 0 sẽ như thế nào? (theo cả hai cách đệ quy và không đệ quy).
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
Câu hỏi 2 trang 71 Chuyên đề Tin học 12: Với đồ thị Hình 14.3 thì thứ tự các đỉnh đã duyệt theo chiều sâu, bắt đầu từ đỉnh 0 sẽ như thế nào? (theo cả hai cách đệ quy và không đệ quy).
Lời giải:
Giả sử rằng chúng ta bắt đầu duyệt từ đỉnh 0, thứ tự các đỉnh được duyệt theo chiều sâu (DFS) sẽ như sau:
- Duyệt đệ quy (Recursive):
Thứ tự duyệt có thể là: 0 -> 2 -> 4 -> 5 -> 1 -> 3 -> 6 -> 7 -> 8
- Duyệt không đệ quy (Non-recursive):
Sử dụng ngăn xếp (stack), thứ tự duyệt có thể là: 0 -> 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 -> 8
Cả hai phương pháp đều cho kết quả giống nhau vì đây là đồ thị dạng cây và chỉ có một đường đi từ một đỉnh đến đỉnh khác mà không cần quay lui.
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: