Phân nhóm người nghi nhiễm Covid-19 trang 69 Chuyên đề Tin học 12

Giải Chuyên đề Tin 12 Bài 5: Thực hành duyệt đồ thị - Cánh diều

Bài toán trang 69 Chuyên đề Tin học 12: Phân nhóm người nghi nhiễm Covid-19

Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1. Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm FO, những người tiếp xúc với người ở nhóm FO sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm 1-1 sẽ được xếp vào nhóm 12,....

Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19.

Lời giải:

Dùng măng hàng đợi Q đề thăm các đỉnh theo chiều rộng, máng level để ghi nhận nhóm nghi nhiễm, Hình 2, 3, 4 mô tá ba bước đầu tiên trong quá trình thực hiện.

Mã giả để thực hiện nhiệm vụ phân nhóm người nghi nhiễm COVID-19 bằng thuật toán duyệt đồ thị theo chiều rộng (BFS):

from collections import deque

# Biểu diễn đồ thị bằng danh sách kề

graph = {

   0: [1, 2],

   1: [0, 3],

   2: [0, 4, 5],

   3: [1, 6],

   4: [2],

   5: [2],

   6: [3]

}

# Hàm thực hiện BFS để phân nhóm

def bfs_covid_contact_tracing(graph, start):

   # Khởi tạo hàng đợi và danh sách nhóm

   queue = deque([start])

   levels = {start: 'FO'}  # Người 0 thuộc nhóm FO

   visited = {start}

   # Duyệt đồ thị

   while queue:

        vertex = queue.popleft()

        for neighbour in graph[vertex]:

            if neighbour not in visited:

                visited.add(neighbour)

                queue.append(neighbour)

                # Phân nhóm dựa trên nhóm của người tiếp xúc

                levels[neighbour] = 'F1' if levels[vertex] == 'FO' else 'F2'

   return levels

# Gọi hàm và in kết quả

levels = bfs_covid_contact_tracing(graph, 0)

for person, level in levels.items():

   print(f'Người {person} thuộc nhóm {level}')

Lời giải bài tập Chuyên đề Tin 12 Bài 5: Thực hành duyệt đồ thị hay, chi tiết khác:

• Vận dụng trang 69 Chuyên đề Tin học 12: Bài toán Tìm đường đi trong mê cung ....

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 4: 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

---