Em hãy minh hoạ duyệt theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1)

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

Câu hỏi trang 68 Chuyên đề Tin học 12: Em hãy minh hoạ duyệt theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1) và bắt đầu từ đỉnh 2.

Lời giải:

Duyệt theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1) và bắt đầu từ đỉnh 2:

1. Duyệt đỉnh 2, thêm đỉnh 2 vào ngăn xếp

2

Đã duyệt

 

2

 

Stack

2. 1. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 3 của đỉnh 2 chưa duyệt. Duyệt đỉnh 3 và thêm đỉnh này vào ngăn xếp.

2

3

Đã duyệt

 

3

2

 

Stack

 

2. 2. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh 3 không có đỉnh kề chưa duyệt. Lấy đỉnh D ra khỏi ngăn xếp.

2

3

Đã duyệt

 

2

 

Stack

 

3. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 0 của đỉnh 2 chưa duyệt. Duyệt đỉnh 0 và thêm đỉnh này vào ngăn xếp.

2

3

4

0

Đã duyệt

 

0

4

2

 

Stack

4. Xem đỉnh 0 ở đỉnh ngăn xếp. Đỉnh kề 5 của đỉnh 0 chưa duyệt. Duyệt đỉnh 5 và thêm đỉnh này vào ngăn xếp.

2

3

4

0

5

Đã duyệt

 

5

0

4

2

 

Stack

 

 

 

5. Xem đỉnh 5 ở đỉnh ngăn xếp. Đỉnh kề 1 của đỉnh 5 chưa duyệt. Duyệt đỉnh 1 và thêm đỉnh này vào ngăn xếp.

2

3

4

0

1

Đã duyệt

 

1

0

4

3

2

 

Stack

 

 

 

 

 

6. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh 1 không có đỉnh chưa duyệt. Lấy đỉnh 1 ra khỏi ngăn xếp.

2

3

4

0

1

Đã duyệt

 

0

4

3

2

 

Stack

 

 

 

7. Xem đỉnh 0 ở đỉnh ngăn xếp. Đỉnh 0 không có đỉnh chưa duyệt. Lấy đỉnh 0 ra khỏi ngăn xếp.

2

3

4

0

1

Đã duyệt

 

4

3

2

 

Stack

 

 

7. Xem đỉnh 4 ở đỉnh ngăn xếp. Đỉnh 4 không có đỉnh chưa duyệt. Lấy đỉnh 4 ra khỏi ngăn xếp.

2

3

4

0

1

Đã duyệt

 

3

2

 

Stack

 

8. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh 3 không có đỉnh chưa duyệt. Lấy đỉnh 3 ra khỏi ngăn xếp.

2

3

4

0

1

Đã duyệt

 

2

 

Stack

9. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh 2 không có đỉnh chưa duyệt. Lấy đỉnh 2 ra khỏi ngăn xếp.

2

3

4

0

1

Đã duyệt

 

Stack

10. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thi theo chiều sâu  là 2,3,4,0,1

2

3

4

0

1

Đã 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:

• Khởi động trang 64 Chuyên đề Tin học 12: Cho đồ thị G1 như ở Hình 1. Hãy tìm đường đi ngắn nhất từ đỉnh H đến đỉnh D ....

• 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 ....

• 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 ....

• 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ị ....

• Thực hành trang 70 Chuyên đề Tin học 12: Nhiệm vu: Duyệt đồ thị theo chiều sâu ....

• Vận dụng trang 71 Chuyên đề Tin học 12: Nhiệm vụ. Kiểm tra đô thị liên thông ....

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:

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

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

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---