Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1)
Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1). Theo em, có tồn tại một hành trình đi từ địa điểm D đến địa điểm G sao cho phải đi qua ít địa điểm trung gian nhất không? Chỉ ra hành trình đó.
Giải Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng - Chân trời sáng tạo
Khởi động trang 59 Chuyên đề Tin học 12: Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1). Theo em, có tồn tại một hành trình đi từ địa điểm D đến địa điểm G sao cho phải đi qua ít địa điểm trung gian nhất không? Chỉ ra hành trình đó.
Lời giải:
Dựa vào mô tả của đồ thị trong Hình 1, có một hành trình từ địa điểm D đến địa điểm G với ít địa điểm trung gian nhất. Hành trình ngắn nhất là:
Hành trình từ D đến G:
Đi từ D -> E
Tiếp tục từ E -> G
Đây là hành trình tối ưu nhất với chỉ một địa điểm trung gian là E. Đường đi này giúp rút ngắn thời gian và quãng đường di chuyển giữa hai địa điểm D và G.
Lời giải bài tập Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng hay, chi tiết khác: