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

Ra mắt Sách 20 đề THPT quốc gia form 2025 toán, văn, anh.... (từ 80k/1 cuốn)

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.

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

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:

Quảng cáo

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:

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

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official