Tìm kiếm theo chiều rộng — Breadth-First Search
Tìm kiếm theo chiều rộng (BFS) duyệt đồ thị hoặc cây theo từng tầng: thăm hết các đỉnh cách nguồn một bước, rồi hai bước, và cứ thế — dùng một hàng đợi (queue) để giữ thứ tự.
Vì duyệt theo lớp, BFS cho ra đường đi ngắn nhất trên đồ thị không trọng số. Cần một tập "đã thăm" để tránh lặp vô hạn khi có chu trình; bộ nhớ tệ nhất tỉ lệ với độ rộng của một tầng.
Như quân ra trận theo từng vòng cờ tướng — hết vòng này mới sang vòng kế.
- Duyệt theo tầng, đảm bảo đường ngắn nhất trên đồ thị không trọng số.
- Giống tin nhắn lan ra: mỗi người nhận tin nhắn truyền cho hàng xóm trước khi hàng xóm truyền tiếp.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Tìm kiếm theo chiều rộng
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| đường ngắn nhất | BFS dùng cho đồ thị không trọng số |
| duyệt theo tầng | Quét cây / đồ thị theo từng tầng |
| lan toả từ điểm | Tìm vùng kết nối, flood fill |
| số bước nhỏ nhất | BFS tự nhiên cho bài min-steps |
Khi nào dùng
3 tình huống điển hình cần nghĩ đến chủ đề này
Cần tìm đường đi ngắn nhất trên đồ thị không trọng số
Cần duyệt theo tầng (level-order) trên cây hoặc đồ thị
Bài toán "lan rộng" từ một nguồn: khoảng cách tối thiểu, số bước nhỏ nhất
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Đồ thị có cạnh weight khác nhau và cần shortest path: dùng Dijkstra / Bellman-Ford
Bài cần khám phá sâu trước (tìm 1 path bất kỳ, backtracking): DFS phù hợp hơn
Đồ thị rất rộng làm queue phình to: cân nhắc iterative deepening DFS
Hình minh hoạ
Chỉnh dữ liệu rồi bấm Phát để xem từng bước.
// BFS lặp — duyệt theo tầngconst queue = [start], visited = new Set()while (queue.length) {const node = queue.shift()visited.add(node)for (const nb of adj[node]) {if (!visited.has(nb)) queue.push(nb)}}
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function bfs(start: Node, graph: Graph): R {
const queue: Node[] = [start]
const visited = new Set<Node>([start])
while (queue.length > 0) {
const node = queue.shift()!
// Xử lý node
visit(node)
// Đưa neighbor chưa thăm vào queue
for (const next of graph.neighbors(node)) {
if (!visited.has(next)) {
visited.add(next)
queue.push(next)
}
}
}
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Dùng hàng đợi (queue, FIFO) — phân biệt với DFS dùng ngăn xếp
Đánh dấu visited TRƯỚC khi push vào queue để tránh lặp (không phải khi pop)
BFS đảm bảo thứ tự tầng → đường đến mỗi node là ngắn nhất trong đồ thị không trọng số
Đếm số tầng bằng cách xử lý trọn một "lớp" queue mỗi vòng (lưu queue.length trước khi duyệt)
Lỗi thường gặp
Đánh dấu visited khi pop thay vì khi push → node có thể vào queue nhiều lần, gây trùng
Nhầm BFS với DFS: BFS dùng queue, DFS dùng stack hoặc đệ quy
Quên xử lý đồ thị có chu trình (phải có set visited)
Độ phức tạp
Time O(V + E), Space O(V) — V là số đỉnh, E là số cạnhBài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay