Câu hỏi:
04/10/2024 92
Từ đồ thị G1 trong Hình 1. Hãy thực hiện yêu cầu sau:
a. Dùng thuật toán duyệt đồ thị theo chiều rộng để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh của đồ thị.
b. Từ câu a, mô tả cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C.
Từ đồ thị G1 trong Hình 1. Hãy thực hiện yêu cầu sau:
a. Dùng thuật toán duyệt đồ thị theo chiều rộng để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh của đồ thị.
b. Từ câu a, mô tả cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C.
Câu hỏi trong đề:
Chuyên đề Tin 12 CTST Bài 3.3. Duyệt đồ thị theo chiều rộng !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
a. Để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh khác trong đồ thị G1 bằng thuật toán duyệt theo chiều rộng (BFS), ta thực hiện các bước sau:
Bắt đầu từ đỉnh C.
Thăm tất cả các đỉnh kề với C trước khi chuyển sang các đỉnh ở cấp độ tiếp theo.
Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.
b. Cách duyệt cây theo chiều rộng từ đỉnh C:
Bắt đầu từ đỉnh C, thăm các đỉnh kề theo thứ tự từ trái sang phải hoặc từ trên xuống dưới.
Đảm bảo rằng mỗi cấp độ của cây được duyệt hoàn toàn trước khi chuyển sang cấp độ tiếp theo.
Ghi nhớ các đỉnh đã thăm để tránh thăm lại.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị G, ở Hình 2.
Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị G, ở Hình 2.
Xem đáp án »
04/10/2024
71
Câu 2:
Cho hai đồ thị G3 (Hình 3) và G4 (Hình 4). Dùng thuật toán duyệt đồ thị theo chiều rộng để
thực hiện hai yêu cầu sau:
- Liệt kê thứ tự duyệt các đỉnh của đồ thị G3 xuất phát từ đỉnh A.
- Cho biết đường đi từ đỉnh F đến đỉnh J trong đồ thị G4 ?
Cho hai đồ thị G3 (Hình 3) và G4 (Hình 4). Dùng thuật toán duyệt đồ thị theo chiều rộng để
thực hiện hai yêu cầu sau:
- Liệt kê thứ tự duyệt các đỉnh của đồ thị G3 xuất phát từ đỉnh A.
- Cho biết đường đi từ đỉnh F đến đỉnh J trong đồ thị G4 ?
Xem đáp án »
04/10/2024
66
Câu 3:
Viết chương trình đếm số nước liên minh với nước đã cho
Yêu cầu: Có N nước, các nước được chia thành các liên minh. Quan hệ liên minh như sau:
nếu nước A liên minh với nước B, nước B liên minh với nước C thì nước A liên minh với nước C. Cho biết nước X, sử dụng thuật toán duyệt đồ thị theo chiều rộng, hãy cho biết có bao nhiêu nước liên minh với nước X.
Dữ liệu vào: Tệp lienminh.txt chứa dữ liệu của các nước. Hàng đầu tiên là danh sách các nước. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai nước liên minh. Hàng cuối cùng là nước X.
Dữ liệu ra: Số nước liên minh với nước X.
Viết chương trình đếm số nước liên minh với nước đã cho
Yêu cầu: Có N nước, các nước được chia thành các liên minh. Quan hệ liên minh như sau:
nếu nước A liên minh với nước B, nước B liên minh với nước C thì nước A liên minh với nước C. Cho biết nước X, sử dụng thuật toán duyệt đồ thị theo chiều rộng, hãy cho biết có bao nhiêu nước liên minh với nước X.
Dữ liệu vào: Tệp lienminh.txt chứa dữ liệu của các nước. Hàng đầu tiên là danh sách các nước. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai nước liên minh. Hàng cuối cùng là nước X.
Dữ liệu ra: Số nước liên minh với nước X.
Xem đáp án »
04/10/2024
66
Câu 4:
Chương trình dưới đây duyệt đồ thị G3 (Hình 3) bắt đầu từ đỉnh B và đỉnh F. Em có nhận xét gì về thứ tự duyệt bắt đầu với đỉnh B và đỉnh F.
Chương trình dưới đây duyệt đồ thị G3 (Hình 3) bắt đầu từ đỉnh B và đỉnh F. Em có nhận xét gì về thứ tự duyệt bắt đầu với đỉnh B và đỉnh F.
Xem đáp án »
04/10/2024
61
Câu 5:
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 đó.
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 đó.
Xem đáp án »
04/10/2024
54
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
về câu hỏi!