Dùng thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 1. Hãy cho biết thứ tự duyệt
Dùng thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 1. Hãy cho biết thứ tự duyệt các đỉnh của đồ thị ở Hình 4.
Giải Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu - Chân trời sáng tạo
Luyện tập 1 trang 70 Chuyên đề Tin học 12: Dùng thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 1. Hãy cho biết thứ tự duyệt các đỉnh của đồ thị ở Hình 4.
Lời giải:
1. Duyệt đỉnh 1, thêm đỉnh 1 vào ngăn xếp
|
1 |
|
|
|
|
|
Đã duyệt
|
1 |
Stack
2. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh kề 7 của đỉnh 1 chưa duyệt. Duyệt đỉnh 7 thêm đỉnh này vào ngăn xếp.
|
1 |
7 |
|
|
|
|
Đã duyệt
|
7 |
|
1 |
Stack
3. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 2 của đỉnh 7 chưa duyệt. Duyệt đỉnh 2 thêm đỉnh này vào ngăn xếp.
|
1 |
7 |
2 |
|
|
|
Đã duyệt
|
2 |
|
7 |
|
1 |
Stack
4. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 3 của đỉnh 2 chưa duyệt. Duyệt đỉnh 3 thêm đỉnh này vào ngăn xếp.
|
1 |
7 |
2 |
3 |
|
|
Đã duyệt
|
3 |
|
2 |
|
7 |
|
1 |
Stack
5. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 4 của đỉnh 3 chưa duyệt. Duyệt đỉnh 4 thêm đỉnh này vào ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
|
Đã duyệt
|
4 |
|
3 |
|
2 |
|
7 |
|
1 |
Stack
6. Xem đỉnh 4 ở đỉnh ngăn xếp. Đỉnh kề 4 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 4 ra khỏi ngăn xếp ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
|
Đã duyệt
|
3 |
|
2 |
|
7 |
|
1 |
Stack
7. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 5 của đỉnh kề 3 chưa duyệt. Duyệt đỉnh 5 vào ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
|
Đã duyệt
|
5 |
|
3 |
|
2 |
|
7 |
|
1 |
Stack
8. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 6 của đỉnh kề 7 chưa được duyệt. Duyệt đỉnh 6 ra vào ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
|
Đã duyệt
|
6 |
|
3 |
|
2 |
|
7 |
|
1 |
Stack
9. Xem đỉnh 6 ở đỉnh ngăn xếp. Đỉnh kề 6 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 6 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
Đã duyệt
|
3 |
|
2 |
|
7 |
|
1 |
Stack
10. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 8 của đỉnh kề 7 chưa duyệt. Duyệt đỉnh 8 vào ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
|
8 |
|
3 |
|
2 |
|
7 |
|
1 |
Stack
11. Xem đỉnh 8 ở đỉnh ngăn xếp. Đỉnh kề 8 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 8 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
|
3 |
|
2 |
|
7 |
|
1 |
Stack
12. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 3 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 3 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
|
2 |
|
7 |
|
1 |
Stack
13. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 2 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 2 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
|
7 |
|
1 |
Stack
14. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 7 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
|
1 |
Stack
15. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh kề 1 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
Stack
16. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là:
|
1 |
7 |
2 |
3 |
4 |
5 |
6 |
8 |
Đã duyệt
Lời giải bài tập Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu hay, chi tiết khác: