Phân nhóm người nghi nhiễm Covid-19 trang 69 Chuyên đề Tin học 12
Phân nhóm người nghi nhiễm Covid-19
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: