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.
3/6
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.
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