Câu hỏi:
26/06/2024 22Vớ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).
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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?
Câu 2:
Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Câu 3:
Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.
Câu 4:
Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.
Câu 5:
Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt sẽ in ra các bước với thông tin sau:
– Thông tin ngăn xếp (hiện thời).
– Phần tử được lấy ra từ ngăn xếp.
– Phần tử được đánh dấu để chuẩn bị cho bước sau (mark).
Câu 6:
Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.
Câu 7:
Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không?
về câu hỏi!