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

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:

• Khởi động trang 62 Chuyên đề Tin học 12: Có 5 bạn A, B, C, D và E, biết rằng A có số điện thoại của C và D, do đó A có thể liên lạc với C ....

• Câu hỏi tự kiểm tra trang 68 Chuyên đề Tin học 12: Trong các câu sau đây, những câu nào đúng khi nói về duyệt đồ thị ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài 1: Đồ thị, phân loại đồ thị

• Chuyên đề Tin học 12 Bài 2: Biểu diễn đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 5: Thực hành duyệt đồ thị

• Chuyên đề Tin học 12 Bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---