Viết lại hàm BFS() in ra các đỉnh đã duyệt. Áp dụng vào đồ thị trong bài để kiểm tra thứ tự các đỉnh đã duyệt có đúng như phần mô phỏng thủ công các hoạt động trên không.

Gợi ý tổng quát của hàm BFS, mà ngoài việc duyệt qua các đỉnh, nó cũng in ra các đỉnh đã được duyệt.

from collections import deque

def BFS(graph, start):

    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 graph[vertex]:  # Duyệt qua các đỉnh kề của đỉnh hiện tại

                if 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 danh sách kề

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

}

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

BFS(graph, 'A')

• Lưu ý: Trong hàm BFS này, sau khi một đỉnh được lấy ra từ hàng đợi và trước khi thêm các đỉnh kề vào hàng đợi, chúng ta kiểm tra xem đỉnh đã được duyệt trước đó hay chưa. Nếu đỉnh chưa được duyệt, ta in ra nó và đánh dấu là đã duyệt. Điều này đảm bảo rằng mỗi đỉnh chỉ được in ra một lần.