Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán

Trang trước Trang sau

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.

Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán

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:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học