Động lực

BFS sử dụng hàng đợi (vào trước, ra trước) để xử lý các đỉnh theo đúng thứ tự chúng được phát hiện, nhờ đó khám phá từng lớp một.

Tại sao nên học BFS?

• Đường đi ngắn nhất: trong đồ thị không trọng số, BFS tìm đường đi có ít cạnh nhất từ đỉnh bắt đầu đến mọi đỉnh khác.
• Đơn giản và tuyến tính: thuật toán chạy trong O(V + E) khi sử dụng hàng đợi và dấu đánh dấu đã thăm.
• Ứng dụng rộng rãi: tìm số bước nhảy ngắn nhất trong mạng, tìm đường biến đổi từ này sang từ khác, giải mê cung và duyệt cây theo thứ tự từng tầng đều sử dụng BFS.

Cũng như DFS, chúng ta đưa các đỉnh kề vào hàng đợi theo thứ tự tăng dần để kết quả dễ dự đoán.