Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán
Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán duyệt đồ thị theo chiều sâu trong đồ thị G5.
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 2 trang 70 Chuyên đề Tin học 12: Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán duyệt đồ thị theo chiều sâu trong đồ thị G5.
Lời giải:
1. Duyệt đỉnh F, thêm đỉnh F vào ngăn xếp
|
F |
|
|
|
|
|
Đã duyệt
|
F |
Stack
2. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh kề B của đỉnh F chưa duyệt. Duyệt đỉnh B thêm đỉnh này vào ngăn xếp.
|
F |
B |
|
|
|
|
Đã duyệt
|
B |
|
F |
Stack
3. Xem đỉnh B ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh B chưa duyệt. Duyệt đỉnh H thêm đỉnh này vào ngăn xếp.
|
F |
B |
H |
|
|
|
Đã duyệt
|
H |
|
B |
|
F |
Stack
3. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh kề J của đỉnh H chưa duyệt. Duyệt đỉnh J thêm đỉnh này vào ngăn xếp.
|
F |
B |
H |
J |
|
|
Đã duyệt
|
J |
|
H |
|
B |
|
F |
Stack
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: