Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận
Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận kể như Hình 13. Em áp dụng thuật toán duyệt theo chiều rộng hoặc theo chiều sâu để chỉ ra các địa điểm có thế đến được nếu xuất phát địa điểm 0 và chỉ sử dụng các tuyến xe buýt này
Giải Chuyên đề Tin 12 Bài 4: Duyệt đồ thị - Cánh diều
Vận dụng trang 68 Chuyên đề Tin học 12: Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận kể như Hình 13. Em áp dụng thuật toán duyệt theo chiều rộng hoặc theo chiều sâu để chỉ ra các địa điểm có thế đến được nếu xuất phát địa điểm 0 và chỉ sử dụng các tuyến xe buýt này
Lời giải:
Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận kể như Hình 13. Em áp dụng thuật toán duyệt theo chiều rộng hoặc theo chiều sâu để chỉ ra các địa điểm có thế đến được nếu xuất phát địa điểm 0 và chỉ sử dụng các tuyến xe buýt này như sau:
* Duyệt theo chiều rộng (BFS) như sau:
Chúng ta sẽ sử dụng BFS để tìm các địa điểm có thể đến được từ địa điểm 0.
- Khởi tạo: Đặt một hàng đợi để lưu trữ các địa điểm cần khám phá. Bắt đầu với địa điểm 0. Đánh dấu địa điểm 0 là đã được thăm. Tạo một danh sách để lưu trữ các địa điểm đã đến được.
- Thuật toán: Lặp lại cho đến khi hàng đợi rỗng:
+ Lấy địa điểm đầu tiên ra khỏi hàng đợi.
+ Khám phá tất cả các địa điểm kết nối trực tiếp với địa điểm hiện tại (theo ma trận kề).
+ Nếu địa điểm chưa được thăm, thêm nó vào hàng đợi và đánh dấu là đã thăm.
* Mã giả cho BFS
def bfs(graph, start):
visited = [False] * len(graph)
queue = []
reachable = []
queue.append(start)
visited[start] = True
while queue:
node = queue.pop(0)
reachable.append(node)
for i in range(len(graph[node])):
if graph[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
return reachable
# Ma trận kề
graph = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 1, 1, 0]
]
# Xuất phát từ địa điểm 0
start = 0
reachable_locations = bfs(graph, start)
print("Các địa điểm có thể đến được từ địa điểm 0:", reachable_locations)
Kết quả như sau: Các địa điểm có thể đến được từ địa điểm 0 là: [0, 1, 3, 2]
Lời giải bài tập Chuyên đề Tin 12 Bài 4: Duyệt đồ thị hay, chi tiết khác: