Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.

Viết lại hàm BFS sử dụng ma trận kề A thay vì danh sách kề Adj. Dưới đây là cách triển khai:

from collections import deque

def BFS(graph, start):

    n = len(graph)

    visited = [False] * n

    visited[start] = True

    queue = deque([start])

    while queue:

        vertex = queue.popleft()

        print("Visit:", vertex)

        for neighbor in range(n):

            if graph[vertex][neighbor] == 1 and not visited[neighbor]:

                visited[neighbor] = True

                queue.append(neighbor)

# Ma trận kề mẫu

graph_matrix = [

    [0, 1, 1, 0, 0, 0],

    [1, 0, 0, 1, 1, 0],

    [1, 0, 0, 0, 0, 1],

    [0, 1, 0, 0, 0, 0],

    [0, 1, 0, 0, 0, 1],

    [0, 0, 1, 0, 1, 0]

]

# Thực hiện BFS từ đỉnh 0

BFS(graph_matrix, 0)

• Trong hàm BFS này, chúng ta duyệt qua các hàng của ma trận kề để xác định các đỉnh kề của mỗi đỉnh. Nếu có một đỉnh kề chưa được duyệt, chúng ta đánh dấu đỉnh đó đã được thăm và thêm nó vào hàng đợi để duyệt tiếp.