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.

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}')