Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng trang 75 Chuyên đề Tin học 12

Nhiệm vụ 1 trang 75 Chuyên đề Tin học 12: Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng

Yêu cầu: Bản đồ mô tả đường đi giữa các địa điểm du lịch trong một thành phố được biểu diễn như ở Hình 1. Dựa vào thuật toán duyệt đồ thị theo chiều rộng được biểu diễn bằng ma trận kể, em hãy viết chương trình tìm đường đi từ địa điểm A đến địa điểm D sao cho đi qua ít địa điểm nhất.

Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.

Dữ liệu ra: Các đỉnh của đường đi từ đỉnh A đến đỉnh D.

Lời giải:

Thuật toán duyệt đô thị theo chiều rộng:

#Duyệt đồ thị G bắt đầu từ đỉnh u def bft (G, u):

đại anh từ trời sáng tạo

Tạo hàng đợi 2 rỗng

Đánh dấu đỉnh u đã duyệt Thêm đỉnh u vào hàng đợi Q while hàng đợi Q khác rỗng: Lấy đính u từ hàng đợi Q xử lí đỉnh

#Thêm các đỉnh kề v của đỉnh u vào hàng đợi a for đỉnh v thuộc tập đỉnh kề của đỉnh u:

if đỉnh v chưa duyệt:

Đánh dấu đỉnh v đã duyệt

Thêm đỉnh v vào hàng đợi Q

Khi đó, thủ tục thực hiện duyệt đồ thị G = (V, E) theo chiều rộng như sau:

#Duyệt đồ thị G theo chiều rộng

def bfs (G):

#Đánh dấu các đỉnh của đồ thị G chưa duyệt

for đỉnh u thuộc đô thị G:

Đánh dấu đỉnh u chưa duyệt

#Duyệt các đỉnh của đồ thị G for đỉnh u thuộc của đô thị 6: if đỉnh u chưa duyệt:

bft (G, u)

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:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 12 hay khá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