Chúng ta đã làm quen với thuật toán duyệt đồ thị theo chiều sâu, quá trình duyệt đi

Giải Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng - Kết nối tri thức

Khởi động trang 75 Chuyên đề Tin học 12: Chúng ta đã làm quen với thuật toán duyệt đồ thị theo chiều sâu, quá trình duyệt đi "sâu" nhất có thể theo các cạnh của đồ thị. Ngoài ra còn có cách duyệt đồ thị theo chiều rộng, được hình dung như khi đổ nước xuống một sàn nhà phẳng, nước sẽ lan toả ra xung quanh theo các hình tròn đồng tâm. Cách duyệt theo chiều rộng có thể được mô phỏng như Hình 16.12.

Giả sử ta bắt đầu duyệt từ đỉnh 0 của đồ thị Hình 16.1b theo chiều rộng. Theo em, chúng ta sẽ duyệt các đỉnh theo nguyên tắc nào và duyệt theo thứ tự nào?

Lời giải:

Thuật toán duyệt theo chiều rộng (BFS) bắt đầu từ một đỉnh và duyệt qua tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang các đỉnh kề của các đỉnh đã duyệt. Khi duyệt từ đỉnh 0 của đồ thị Hình 16.1b, chúng ta sẽ tuân theo nguyên tắc sau:

- Nguyên tắc duyệt:

+ Duyệt tất cả các đỉnh kề với đỉnh hiện tại trước khi chuyển sang đỉnh kề tiếp theo.

+ Sử dụng hàng đợi (queue) để lưu trữ thứ tự duyệt.

- Thứ tự duyệt có thể là:

+ Bắt đầu từ đỉnh 0, thăm tất cả các đỉnh kề với đỉnh 0.

+ Sau đó, duyệt qua các đỉnh kề với các đỉnh đã thăm theo thứ tự từ hàng đợi.

+ Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.

Lời giải bài tập Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng hay, ngắn gọn khác:

• Hoạt động 1 trang 75 Chuyên đề Tin học 12: Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0 ....

• Câu hỏi 1 trang 76 Chuyên đề Tin học 12: Mệnh đề sau đúng hay sai? Giả sử gọi BFS(Adj,s) là chương trình duyệt đồ thị ....

• Câu hỏi 2 trang 76 Chuyên đề Tin học 12: Trả lời các câu hỏi dựa trên đồ thị Hình 16.2. Các đỉnh kề với a là đỉnh nào? ....

• Hoạt động 2 trang 77 Chuyên đề Tin học 12: Tìm hiểu, thảo luận về cách cài đặt thuật toán theo chiều rộng ....

• Câu hỏi 1 trang 79 Chuyên đề Tin học 12: Thứ tự các đỉnh có trong danh sách đỉnh kề Adj có ảnh hưởng đến thứ tự các đỉnh ....

• Câu hỏi 2 trang 79 Chuyên đề Tin học 12: Cho đồ thị Hình 16.4. Nếu thực hiện duyệt theo chiều sâu và chiều rộng ....

• Luyện tập 1 trang 79 Chuyên đề Tin học 12: Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề ....

• Luyện tập 2 trang 79 Chuyên đề Tin học 12: Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề ....

• Vận dụng 1 trang 79 Chuyên đề Tin học 12: Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS ....

• Vận dụng 2 trang 79 Chuyên đề Tin học 12: Cho đơn đô thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

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

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

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)

---