Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.

Gợi ý viết tổng quát của hàm BFS sử dụng ma trận kề của đồ thị:

from collections import deque

def BFS(matrix, start):

    n = len(matrix)  # Số lượng đỉnh trong đồ thị

    visited = set()  # Sử dụng một set để lưu trữ các đỉnh đã được duyệt

    queue = deque([start])  # Khởi tạo hàng đợi và thêm đỉnh bắt đầu vào đó

    while queue:

        vertex = queue.popleft()  # Lấy đỉnh ở đầu hàng đợi ra

        if vertex not in visited:

            print("Visit:", vertex)  # In ra đỉnh đã duyệt

            visited.add(vertex)  # Đánh dấu đỉnh đã duyệt

 

            for neighbor in range(n):  # Duyệt qua tất cả các đỉnh

                if matrix[vertex][neighbor] == 1 and neighbor not in visited:

                    queue.append(neighbor)  # Thêm các đỉnh kề chưa được duyệt vào hàng đợi

# Đồ thị mẫu dưới dạng ma trận kề

graph_matrix = [

    [0, 1, 1, 0, 0, 0],  # A

    [1, 0, 0, 1, 1, 0],  # B

    [1, 0, 0, 0, 0, 1],  # C

    [0, 1, 0, 0, 0, 0],  # D

    [0, 1, 0, 0, 0, 1],  # E

    [0, 0, 1, 0, 1, 0]   # F

]

# Thực hiện BFS từ đỉnh 0 (tương ứng với đỉnh 'A')

BFS(graph_matrix, 0)

- Chú ý: Trong hàm BFS này, ta sử dụng ma trận kề matrix để xác định các đỉnh kề của mỗi đỉnh. Nếu một đỉnh kề chưa được duyệt, ta thêm nó vào hàng đợi để duyệt tiếp. Quá trình này được lặp lại cho tất cả các đỉnh kề của mỗi đỉnh được duyệt.