Thuật toán BFS (Breadth-First Search)

Giới thiệu thuật toán

Thuật toán BFS (Breadth-First Search) là một trong những thuật toán cơ bản nhất trong đồ thị, được sử dụng để tìm kiếm đường đi từ một đỉnh (node) bất kỳ đến một đỉnh khác trong đồ thị. Thuật toán BFS được sử dụng rộng rãi trong các ứng dụng thực tế, chẳng hạn như tìm kiếm đường đi trong bản đồ, tìm kiếm đường đi trong trò chơi, tìm kiếm đường đi trong mạng lưới, vv.

Các bước thực hiện thuật toán

Thuật toán BFS được thực hiện theo các bước sau:

1. Bắt đầu từ đỉnh gốc (source), đưa đỉnh này vào hàng đợi (queue).
2. Đánh dấu đỉnh gốc là đã thăm (visited).
3. Lấy ra đỉnh đầu tiên trong hàng đợi và xét tất cả các đỉnh kề với đỉnh này.
4. Nếu đỉnh kề chưa được thăm, đưa đỉnh này vào hàng đợi và đánh dấu là đã thăm.
5. Lặp lại bước 3 và 4 cho đến khi tìm được đỉnh cần tìm kiếm hoặc hàng đợi rỗng.

Ví dụ về thuật toán

Giả sử chúng ta có đồ thị sau:

     1-----2
     |     |
     3-----4

Với đỉnh gốc là 1, ta sẽ thực hiện thuật toán BFS như sau:

1. Đưa đỉnh 1 vào hàng đợi, đánh dấu đỉnh 1 là đã thăm.
2. Lấy đỉnh 1 ra khỏi hàng đợi, xét các đỉnh kề của đỉnh 1 là 2 và 3.
3. Đưa đỉnh 2 và 3 vào hàng đợi, đánh dấu 2 và 3 là đã thăm.
4. Lấy đỉnh 2 ra khỏi hàng đợi, xét các đỉnh kề của đỉnh 2, nhưng không có đỉnh kề nào chưa được thăm.
5. Lấy đỉnh 3 ra khỏi hàng đợi, xét các đỉnh kề của đỉnh 3 là 1 và 4.
6. Đỉnh 1 đã được thăm trước đó, nên ta không thêm vào hàng đợi.
7. Đưa đỉnh 4 vào hàng đợi, đánh dấu 4 là đã thăm.
8. Lấy đỉnh 4 ra khỏi hàng đợi, không có đỉnh kề nào chưa được thăm.
9. Hàng đợi rỗng, thuật toán kết thúc

Cài đặt thuật toán với Python

Để cài đặt thuật toán BFS với Python, ta có thể sử dụng một danh sách liên kết (adjacency list) để lưu trữ đồ thị và sử dụng một hàng đợi (queue) để lưu trữ các đỉnh cần thăm.

Ví dụ sau đây minh họa cách cài đặt thuật toán BFS với Python:

from collections import defaultdict, deque

# Hàm BFS
def BFS(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Khởi tạo đồ thị
graph = defaultdict(list)
graph[1] = [2, 3]
graph[2] = [1, 4]
graph[3] = [1, 4]
graph[4] = [2, 3]

# Thực hiện thuật toán BFS
BFS(graph, 1)

Kết quả sẽ là: 1, 2, 3, 4

Đánh giá độ phức tạp của thuật toán

Độ phức tạp của thuật toán BFS là O(V + E), trong đó V là số đỉnh trong đồ thị và E là số cạnh trong đồ thị. Thuật toán này cần phải duyệt qua tất cả các đỉnh và cạnh của đồ thị, do đó độ phức tạp của nó là tuyến tính theo kích thước của đồ thị.