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?

Quảng cá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.

Quảng cáo

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: