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

Trang trước Trang 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.

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

Các sản phẩm khác của Vietjack:

TÀI LIỆU CLC DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, bài giảng powerpoint, đề thi file word có đáp án 2026 tại https://tailieugiaovien.com.vn/

Hỗ trợ zalo: VietJack Official

Tổng đài hỗ trợ đăng ký: 084 283 45 85

500+ đề thi thử tốt nghiệp THPT Quốc gia form 2026 41 tài liệu 100+ đề thi HSA,TSA,V-ACT,BCA,BQP...2026 95 tài liệu Đề thi giữa kì, cuối kì 12 254 tài liệu Chuyên đề dạy thêm Toán, Lí, Hóa... 12 71 tài liệu Đề thi HSG 12 8 tài liệu Bài giảng Powerpoint 12 42 tài liệu
Xem tất cả tài liệu

Công cụ giáo viên (2048.VN)

Tạo- trộn đề thi miễn phí từ file PDF, Word, Giao bài nhanh chóng, Hoàn toàn Free

Tạo đề, số hóa đề thi từ PDF/Word/Excel Nhập đề nhanh, trích xuất nội dung tự động. Trộn đề thành nhiều mã, Download/In đề thi offline Tạo nhiều mã đề khác nhau, xuất file hoặc in dễ dàng. Quản lý lớp học Theo dõi học sinh, điểm số và kết quả học tập trực quan. Giao bài tập, tổ chức thi kiểm tra trực tuyến Giao bài, chấm điểm và thống kê kết quả ngay trên hệ thống.
Khám phá công cụ
Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học