Thuật toán tìm kiếm theo chiều rộng (BFS)

8.1 Nguyên tắc hoạt động của thuật toán BFS

Tìm kiếm theo chiều rộng (Breadth-First Search, BFS) — là một thuật toán dùng để duyệt hoặc tìm kiếm trong đồ thị, bắt đầu từ đỉnh gốc và khám phá tất cả các đỉnh kề ở mức hiện tại trước khi chuyển sang các đỉnh của mức tiếp theo.

Các bước của thuật toán:

1. Bắt đầu từ đỉnh gốc được chọn và đặt nó vào hàng đợi.
2. Trong khi hàng đợi chưa trống, thực hiện các hành động sau:
   • Lấy đỉnh ra khỏi đầu hàng đợi và đánh dấu nó là đã thăm.
   • Với mỗi đỉnh kề chưa thăm, thêm nó vào hàng đợi.
3. Lặp lại bước 2, cho đến khi tất cả các đỉnh có thể đạt từ đỉnh gốc đều đã được thăm.

Hình ảnh minh họa:

Độ phức tạp thời gian:

O(V + E), với V là số lượng đỉnh, E là số lượng cạnh.

Mỗi nút và mỗi cạnh của đồ thị chỉ được thăm một lần.

Độ phức tạp không gian:

O(V), do sử dụng hàng đợi để lưu trữ các đỉnh, cũng như các mảng để lưu trữ trạng thái (các đỉnh đã thăm).

8.2 Triển khai BFS bằng cách sử dụng hàng đợi

Duyệt theo chiều rộng được triển khai tốt với cấu trúc dữ liệu gọi là hàng đợi.

Triển khai BFS bằng cách sử dụng hàng đợi:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Xử lý nút
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Ví dụ sử dụng:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Tìm kiếm theo chiều rộng hai chiều

BFS thường được sử dụng trong các trò chơi, khi cần tìm đường ngắn nhất giữa hai điểm trong một cảnh quan phức tạp. Vấn đề như vậy có thể dễ dàng chuyển thành bài toán tìm đường trong đồ thị giữa hai đỉnh. Các cạnh của đồ thị này là tất cả các đường có thể đi trên bản đồ.

Nhưng để tìm đường nhanh hơn, nó thường được tìm từ hai đầu. Để làm điều này sử dụng BFS hai chiều.

Nguyên tắc hoạt động

Tìm kiếm theo chiều rộng hai chiều (Bidirectional BFS) — là một biến thể được tối ưu hóa của thuật toán BFS, thực hiện hai lượt duyệt đồ thị song song: một từ đỉnh gốc và một từ đỉnh đích. Các lượt duyệt tiếp tục cho đến khi hai lượt duyệt gặp nhau, điều này giúp giảm đáng kể số lượng đỉnh và cạnh cần kiểm tra so với BFS cổ điển.

Các bước của thuật toán:

• Khởi tạo hai hàng đợi: một cho việc duyệt từ đỉnh gốc, và một từ đỉnh đích.
• Khởi tạo hai tập hợp các đỉnh đã thăm để theo dõi các đỉnh đã thăm theo cả hai hướng.
• Thực hiện luân phiên duyệt đồ thị từ hai hàng đợi.
• Tại mỗi bước, kiểm tra xem các tập hợp đỉnh đã thăm có giao nhau không. Nếu có giao nhau, đường đi tồn tại.
• Quá trình tiếp tục cho đến khi tìm thấy nút giao nhau hoặc hàng đợi rỗng.

Độ phức tạp thời gian

Trong trường hợp tốt nhất: O(2 * (V + E)) = O(V + E), với V là số lượng đỉnh, E là số lượng cạnh.

BFS hai chiều thường duyệt số lượng đỉnh ít hơn so với BFS một chiều, đặc biệt trong các đồ thị lớn.

Độ phức tạp không gian:

O(V) để lưu trữ hai hàng đợi và hai tập hợp các đỉnh đã thăm.

Ví dụ triển khai BFS hai chiều

Ví dụ rất dài — thuật toán dài gấp ba lần so với tìm kiếm một chiều — vì vậy mình sẽ không trình bày ở đây. Khi bạn thực sự cần nó, bạn sẽ có khả năng tự viết nó.

8.4 Ví dụ các bài toán giải quyết bằng BFS

Các ví dụ kinh điển về các bài toán giải quyết bằng BFS:

1. Tìm đường ngắn nhất trong đồ thị vô hướng:

BFS được sử dụng để tìm đường ngắn nhất (số lượng cạnh tối thiểu) từ đỉnh gốc đến đỉnh đích trong đồ thị vô hướng.

Ứng dụng:

• Trong các hệ thống dẫn đường để tìm đường ngắn nhất giữa các điểm.
• Trong phân tích mạng để tìm đường ngắn nhất truyền dữ liệu.

2. Kiểm tra tính liên thông của đồ thị:

Kiểm tra xem đồ thị có liên thông hay không, tức là có tồn tại đường đi giữa bất kỳ hai đỉnh nào.

Ứng dụng:

• Trong phân tích mạng để kiểm tra tính liên thông của mạng.
• Trong phân tích mạng xã hội để kiểm tra tính liên thông của nhóm người dùng.

3. Tạo ma trận:

Sử dụng BFS để tạo ra các ma trận ngẫu nhiên với các tính chất cho trước.

Ứng dụng:

• Trong các ứng dụng game để tạo ra các ma trận.
• Trong robot học để kiểm tra các thuật toán dẫn đường.

4. Tìm kiếm theo chiều rộng trong cây:

BFS được dùng để duyệt qua các cây, thực hiện các hành động tại mỗi mức của cây (ví dụ: in tất cả các nút trong mỗi mức).

Ứng dụng:

• Trong các bài toán trực quan hóa dữ liệu, nơi cần hiển thị dữ liệu theo mức.
• Trong các bài toán lập kế hoạch, nơi cần thực hiện các hành động tại mỗi mức của hệ thống phân cấp.

5. Kiểm tra đồ thị hai phía:

Kiểm tra xem đồ thị có phải là đồ thị hai phía không, tức là có thể chia các đỉnh thành hai tập hợp sao cho các cạnh chỉ tồn tại giữa các đỉnh thuộc các tập hợp khác nhau.

Ứng dụng:

• Trong lý thuyết đồ thị để kiểm tra đồ thị hai phía.
• Trong các bài toán tô màu đồ thị, nơi cần kiểm tra xem có thể tô màu đồ thị bằng hai màu hay không.