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

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

Xây dựng đồ thị, đánh số các ô trong mê cung (Hình 6), mỗi ô tương ứng

một đỉnh của đồ thị, hai ô kể cạnh có cạnh nối. Theo như Hình 6, đồ thị có 50 đỉnh. Duyệt đồ thị theo chiều sâu bắt đầu từ ô số 1 theo thứ tự ưu tiên đi theo ô xuống dưới, sang phải, lên trên, sang trái.