Duyệt theo chiều rộng (BFS)

Bạn sẽ học được gì

BFS — Breadth-First Search (duyệt theo chiều rộng) thăm đồ thị theo từng lớp: gần trước, xa sau. Nhờ vậy nó tìm được đường đi ngắn nhất theo số cạnh trên đồ thị không trọng số. Trái tim của BFS là một hàng đợi (queue) và một tập visited.

1. Trực quan: vết dầu loang

Hãy tưởng tượng bạn nhỏ một giọt mực vào mặt nước tại đỉnh xuất phát. Mực lan đều ra mọi hướng: trước tiên thấm tới tất cả các đỉnh cách 1 bước, rồi mới tới những đỉnh cách 2 bước, rồi 3 bước... Đó chính là BFS: nó phủ hết một lớp rồi mới sang lớp tiếp theo.

   Bat dau tu A:

   lop 0:        A
                / \
   lop 1:      B   C
              /|   |
   lop 2:    D E   F

   Thu tu tham: A  B C  D E F
                (gan -> xa, het lop nay moi sang lop sau)

Vì luôn xử lý đỉnh gần nhất trước, lần đầu tiên chạm tới một đỉnh cũng chính là con đường ngắn nhất (ít cạnh nhất) tới đỉnh đó.

2. Cơ chế: queue và visited

BFS dùng hàng đợi FIFO (vào trước ra trước) để đảm bảo lớp gần được lấy ra trước lớp xa. Đồ thị lưu bằng danh sách kề — một dict ánh xạ mỗi đỉnh sang danh sách hàng xóm.

Bước	Hành động
Khởi tạo	Cho đỉnh nguồn vào queue, đánh dấu visited
Lặp	Lấy đỉnh đầu queue ra, duyệt hàng xóm
Mở rộng	Hàng xóm nào chưa thăm thì đánh dấu và đẩy vào queue

Đánh dấu khi ĐẨY VÀO, không phải khi LẤY RA

Đánh dấu visited ngay lúc đưa vào queue. Nếu đợi tới lúc lấy ra mới đánh dấu, một đỉnh có thể bị đẩy vào queue nhiều lần → sai và chậm.

3. Chạy debug: BFS từng bước

🐞 BFS bắt đầu từ ABước 1/8

1g = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
2q = ["A"]; seen = {"A"}; order = []
3while q:
4  u = q.pop(0)
5  order.append(u)
6  for v in g[u]:
7      if v not in seen:
8          seen.add(v)
9          q.append(v)

Biến tại bước này

q	[A]
seen	{A}
order	[]

👉 Nguồn A vào queue, đánh dấu seen.

4. Code chạy được

Dùng collections.deque để popleft() đạt O(1) (nếu dùng list.pop(0) sẽ là O(n)).

Đang tải trình chạy code…

5. Phân tích

Khía cạnh	Giá trị
Thời gian	O(V + E) — mỗi đỉnh và mỗi cạnh xét đúng một lần
Bộ nhớ	O(V) — cho queue và tập visited
Tìm đường ngắn nhất	Đúng trên đồ thị không trọng số

Bẫy thường gặp:

• Quên visited → lặp vô hạn trên đồ thị có chu trình.
• Dùng list.pop(0) thay vì deque → tụt xuống O(V²).
• Đánh dấu lúc lấy ra thay vì lúc đẩy vào → một đỉnh vào queue nhiều lần.

6. Mẫu nhận diện

• "Đường đi ngắn nhất trên lưới / đồ thị không trọng số" → BFS.
• "Tìm theo từng lớp", "ít bước nhất", "số nước cờ tối thiểu" → BFS.
• "Lan toả", "vùng liên thông gần nhất", loang trên bàn cờ → BFS.

7. 🎮 Trò chơi: Hiểu BFS

🎮 Hiểu BFSCâu 1/4· Điểm 0· 🔥 0

BFS duyệt theo lớp, dùng queue FIFO. Lần đầu chạm = đường ngắn nhất theo số cạnh.

BFS dùng cấu trúc dữ liệu nào để chọn đỉnh xử lý tiếp?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Độ phức tạp thời gian của BFS (danh sách kề) là?

2. Vì sao BFS tìm được đường ngắn nhất theo số cạnh?

3. Trong Python nên dùng gì cho queue của BFS?

9. Hoàn thành

…

☑️ Tiếp theo: 3.3.2 — Duyệt theo chiều sâu (DFS) (lao thật sâu rồi quay lui).