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

Trang trước Trang sau

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

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

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