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

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 1 trang 70 Chuyên đề Tin học 12: 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.

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

Quảng cáo

Lời giải:

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

Quảng cáo

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:

Quảng cáo

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:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Nếu thấy hay, hãy động viên và chia sẻ nhé! Các bình luận không phù hợp với nội quy bình luận trang web sẽ bị cấm bình luận vĩnh viễn.


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