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
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ác bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:
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
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ác bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:
- Mức 0: Bản thân đỉnh 0.
- Mức 1: Các đỉnh kề với đỉnh mức 0.
- Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1.
Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa.
Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào.
Lời giải:
Để thực hiện duyệt theo chiều rộng (BFS) từ đỉnh 0 của đồ thị, chúng ta sẽ tuân theo các bước sau:
- Mức 0: Bắt đầu từ đỉnh 0.
- Mức 1: Duyệt tất cả các đỉnh kề với đỉnh 0.
- Mức 2: Duyệt tất cả các đỉnh kề với các đỉnh ở Mức 1 và không phải là đỉnh 0.
- Các Mức tiếp theo: Tiếp tục duyệt các đỉnh kề với đỉnh ở mức trước đó, không lặp lại các đỉnh đã duyệt.
Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh 0 đều được duyệt.
Sự khác biệt chính giữa hai phương pháp duyệt đồ thị theo chiều sâu (DFS) và chiều rộng (BFS) là:
- DFS: Duyệt sâu vào từng nhánh của đồ thị trước khi quay lại (backtrack).
- BFS: Duyệt đồ thị theo từng mức độ rộng, từ gần đến xa so với điểm bắt đầu.
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: