Thuật toán BFS (duyệt theo chiều rộng) là gì: cách hoạt động, code và độ phức tạp

BFS giải bài toán gì

Rất nhiều bài toán thực chất là đồ thị: các trang web và liên kết giữa chúng, bạn bè trong mạng xã hội, các ô trên bàn cờ, các trạng thái của một câu đố. BFS trả lời hai câu hỏi thường gặp trên đồ thị như vậy: từ một nút xuất phát có thể đến được những nút nào, và cần tối thiểu bao nhiêu bước để đến từng nút đó?

Vì BFS lan ra theo các vòng có khoảng cách tăng dần, lần đầu tiên nó chạm tới một nút luôn là theo đường đi có ít cạnh nhất. Vì vậy BFS là thuật toán chuẩn để tìm đường đi ngắn nhất khi mọi cạnh có cùng chi phí.

Ý tưởng bằng lời đơn giản

1. Đưa nút xuất phát vào hàng đợi và đánh dấu là đã thăm.
2. Lấy nút ở đầu hàng đợi ra.
3. Với mỗi nút kề chưa được thăm, đánh dấu là đã thăm và thêm vào cuối hàng đợi.
4. Lặp lại bước 2 và 3 cho đến khi hàng đợi rỗng.

Hãy đánh dấu nút là đã thăm ngay khi thêm vào hàng đợi, không phải khi lấy ra. Nếu không, cùng một nút có thể bị thêm nhiều lần trước khi được xử lý.

Ví dụ từng bước

Xét đồ thị vô hướng sau: A–B, A–C, B–D, C–D, C–E, D–F. Bắt đầu từ A và thăm các nút kề theo thứ tự bảng chữ cái.

Thứ tự thăm là A, B, C, D, E, F. Có thể đến D từ cả B lẫn C, nhưng D chỉ được phát hiện một lần, từ B, vì nó được đánh dấu là đã thăm ngay lúc đó.

Cài đặt bằng Python

Dùng collections.deque làm hàng đợi: popleft() có độ phức tạp O(1), trong khi list.pop(0) là O(n). Đồ thị là một dictionary ánh xạ mỗi nút tới danh sách các nút kề (danh sách kề).

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

Ở đây dictionary dist làm hai việc: vừa là tập các nút đã thăm, vừa lưu kết quả. Để dựng lại đường đi thực tế, hãy lưu thêm nút cha của mỗi nút rồi lần ngược từ đích.

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

Độ phức tạp thời gian và không gian

V là số đỉnh (nút) và E là số cạnh. Nếu dùng ma trận kề thay cho danh sách kề, thời gian trở thành O(V²) vì tìm các nút kề của một nút tốn O(V).

Biến thể và lỗi thường gặp

• BFS trên lưới: coi mỗi ô là một nút và bốn (hoặc tám) ô lân cận là các cạnh. Hãy kiểm tra biên và tường trước khi thêm ô vào hàng đợi.
• BFS đa nguồn: đưa nhiều nút xuất phát vào hàng đợi với khoảng cách 0. Cách này tìm khoảng cách đến nguồn gần nhất, ví dụ lối thoát gần nhất trong mê cung.
• BFS 0-1: khi trọng số cạnh chỉ là 0 hoặc 1, dùng deque và đẩy các nút kề có trọng số 0 lên đầu. Cách này tìm đường đi ngắn nhất trong O(V + E).
• BFS hai chiều: tìm kiếm đồng thời từ điểm xuất phát và điểm đích, dừng khi hai biên gặp nhau. Cách này thường duyệt ít nút hơn nhiều.
• Xử lý từng tầng: ghi lại len(queue) ở đầu mỗi vòng rồi lấy ra đúng chừng đó nút để xử lý một tầng.

Khi nào dùng BFS và ứng dụng thực tế

• Bài phỏng vấn: đường đi ngắn nhất trong mê cung hoặc lưới, word ladder, rotting oranges (BFS đa nguồn), duyệt cây nhị phân theo từng tầng, số nước đi tối thiểu của quân mã.
• Mạng máy tính: tìm mọi thiết bị trong phạm vi k bước nhảy, phát quảng bá trong mạng ngang hàng, gợi ý “những người bạn có thể biết” ở khoảng cách 2 trong đồ thị mạng xã hội.
• Trình thu thập dữ liệu web (web crawler) thăm các trang theo thứ tự khoảng cách liên kết từ một trang gốc.
• Bộ thu gom rác (ví dụ bộ thu gom sao chép của Cheney) và các chương trình giải câu đố cần số nước đi ít nhất.