Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động
Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động thì thứ tự các đỉnh được đánh dấu sẽ theo thứ tự nào?
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 1 trang 71 Chuyên đề Tin học 12: Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động thì thứ tự các đỉnh được đánh dấu sẽ theo thứ tự nào?
Lời giải:
Thứ tự các đỉnh được đánh dấu khi áp dụng thuật toán duyệt theo chiều sâu (DFS) sẽ phụ thuộc vào đỉnh bắt đầu và quy tắc chọn đỉnh kế tiếp khi có nhiều lựa chọn. Nếu giả sử bắt đầu từ đỉnh 0 và chọn đỉnh có số thứ tự nhỏ nhất chưa được thăm, một thứ tự duyệt có thể là:
- Bắt đầu từ đỉnh 0: Đánh dấu đỉnh 0 là đã thăm.
- Tiếp tục đến đỉnh 5: Đánh dấu đỉnh 5 là đã thăm.
- Sau đó đến đỉnh 1: Đánh dấu đỉnh 1 là đã thăm.
- Tiếp tục đến đỉnh 6: Đánh dấu đỉnh 6 là đã thăm.
- Tiếp theo là đỉnh 3: Đánh dấu đỉnh 3 là đã thăm.
- Rồi đến đỉnh 4: Đánh dấu đỉnh 4 là đã thăm.
- Sau đó là đỉnh 2: Đánh dấu đỉnh 2 là đã thăm.
- Cuối cùng là đỉnh 7: Đánh dấu đỉnh 7 là đã thăm.
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: