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

Trang trước Trang sau

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.

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

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:

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