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 đ
4/6
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.
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)