Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học
Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học
Giải Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị - Chân trời sáng tạo
Khởi động trang 72 Chuyên đề Tin học 12: Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học
Lời giải:
Hai thuật toán duyệt đồ thị theo chiều rộng (BFS) và chiều sâu (DFS) là hai thuật toán cơ bản nhất của đồ thị. Các thuật toán này giúp chúng ta “đến thăm” tất cả các cạnh và các đỉnh của đồ thị trong thời gian tối thiểu. Một số bài toán như: Kiểm tra một đồ thị là phân đôi (bi-partite), Tìm đường ngắn nhất trong đồ thị không có trọng số (Single source Shortest path in an unweighted graph), Tìm vòng trong đồ thị vô hướng, Tìm vòng (cycle) trong đồ thị có hướng, Case study: Dò mìn (Minesweeper).
Lời giải bài tập Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị hay, chi tiết khác: