Breadth-first search (BFS) là gì?

Question

Accepted Answer

**BFS** khám phá một đồ thị theo từng tầng (level by level), thăm tất cả các đỉnh kề của một nút trước khi đi sâu hơn. Nó dùng một **queue** (hàng đợi) và tìm **đường đi ngắn nhất** (ít cạnh nhất) trong đồ thị không trọng số.

## Ý tưởng

Bắt đầu từ một nguồn, đưa nó vào hàng đợi, rồi liên tục lấy một nút ra khỏi hàng đợi, thăm các đỉnh kề chưa được thăm của nó, và đưa chúng vào hàng đợi. Một tập `visited` (đã thăm) ngăn việc thăm lại.

## Ví dụ

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: khám phá nút gần nhất trước
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## Độ phức tạp

- **Thời gian:** O(V + E) — mỗi đỉnh và mỗi cạnh một lần.
- **Bộ nhớ:** O(V) cho hàng đợi và tập visited.

## Khi nào dùng / những cạm bẫy

Dùng BFS cho **đường đi ngắn nhất trong đồ thị không trọng số**, duyệt theo tầng (level-order), và tìm các thành phần liên thông. Nó dùng nhiều bộ nhớ hơn DFS (cả một biên giới (frontier) cùng lúc). Luôn theo dõi `visited` nếu không bạn có thể lặp vô hạn trên các chu trình.

## Tại sao điều này quan trọng

BFS là *chính* thuật toán cho đường đi ngắn nhất khi mọi cạnh có trọng số như nhau — định tuyến, thu thập dữ liệu web (web crawling), mức độ phân cách trong mạng xã hội.

Cấu trúc theo tầng dựa trên hàng đợi của nó là một mô thức duyệt cơ bản.

Biết BFS so với DFS cho phép bạn chọn đúng công cụ cho các bài toán về khả năng tiếp cận (reachability), đường đi và thứ tự.