Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu
Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh A của đồ thị G3 ở Hình 3.
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
Câu hỏi trang 69 Chuyên đề Tin học 12: Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh A của đồ thị G3 ở Hình 3.
Lời giải:
1. Duyệt đỉnh A, thêm đỉnh A vào ngăn xếp
|
A |
|
|
|
|
|
Đã duyệt
|
A |
Stack
2. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh A chưa duyệt. Duyệt đỉnh H thêm đỉnh này vào ngăn xếp.
|
A |
H |
|
|
|
|
Đã duyệt
|
H |
|
A |
Stack
3. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh J chưa duyệt. Duyệt đỉnh J thêm đỉnh này vào ngăn xếp.
|
A |
H |
J |
|
|
|
Đã duyệt
|
J |
|
H |
|
A |
Stack
4. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh J không có đỉnh kề chưa duyệt. Lấy đỉnh J ra khỏi ngăn xếp.
|
A |
H |
J |
|
|
|
Đã duyệt
|
H |
|
A |
Stack
5. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh kề G của đỉnh A chưa duyệt. Duyệt đỉnh G, thêm đỉnh này vào ngăn xếp.
|
A |
H |
J |
G |
|
|
Đã duyệt
|
G |
|
H |
|
A |
Stack
6. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh kề I của đỉnh G chưa duyệt. Duyệt đỉnh I, thêm đỉnh này vào ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
I |
|
G |
|
H |
|
A |
Stack
6. Xem đỉnh I ở đỉnh ngăn xếp. Đỉnh I không có đỉnh kề chưa duyệt. Lấy đỉnh I, ra khỏi ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
G |
|
H |
|
A |
Stack
7. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh G có đỉnh kề F chưa duyệt. Thêm đỉnh F vào ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
F |
|
G |
|
H |
|
A |
Stack
8. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh F không có đỉnh kề chưa duyệt. Lấy đỉnh F ra khỏi ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
G |
|
H |
|
A |
Stack
9. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh G không có đỉnh kề chưa duyệt. Lấy đỉnh G ra khỏi ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
H |
|
A |
Stack
10. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh H không có đỉnh kề chưa duyệt. Lấy đỉnh H ra khỏi ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
|
A |
Stack
11. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh A không có đỉnh kề chưa duyệt. Lấy đỉnh A ra khỏi ngăn xếp.
|
A |
H |
J |
G |
I |
|
Đã duyệt
Stack
12. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là:
|
A |
H |
J |
G |
I |
|
Đã 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: