Tổng quan
Breadth-First Search (BFS) khám phá đồ thị hoặc lưới theo từng lớp, thăm mọi ô ở khoảng cách hiện tại trước khi tiến thêm một bước. Vì nó lan ra thành các vòng mở rộng từ điểm xuất phát, lần đầu tiên chạm tới đích cũng là lúc nó tìm được đường đi ngắn nhất trong mọi đồ thị không trọng số.
BFS dùng một hàng đợi FIFO đơn giản và coi mỗi bước di chuyển đều tốn đúng một đơn vị, khiến nó là lựa chọn tự nhiên cho bài toán đường đi ngắn nhất trên lưới đồng nhất.
Tìm kiếm theo chiều rộng (BFS) hoạt động thế nào?
- Đưa nút xuất phát vào hàng đợi FIFO và đánh dấu đã thăm.
- Lấy nút ở đầu hàng đợi ra và xét mọi hàng xóm chưa thăm của nó.
- Đánh dấu mỗi hàng xóm đã thăm, ghi lại nút cha mà nó đến từ đó, rồi đưa vào hàng đợi.
- Lặp lại đến khi đích được lấy ra khỏi hàng đợi, rồi lần theo các liên kết cha để dựng lại đường đi.
Khi nào nên dùng?
- Tìm đường đi ngắn nhất trên lưới và mê cung không trọng số, khi mỗi bước có chi phí bằng nhau.
- Tìm mọi nút trong một số bước cố định, chẳng hạn các ô có thể tới trong trò chơi.
- Ưu tiên Dijkstra hoặc A* khi các cạnh mang trọng số khác nhau.
Phân tích độ phức tạp
BFS thăm mỗi đỉnh một lần và duyệt mỗi cạnh một lần, cho thời gian O(V + E). Nó lưu hàng đợi và tập đã thăm nên bộ nhớ là O(V) — trên lưới rộng có thể rất lớn. Trên đồ thị không trọng số, nó đảm bảo tìm được đường đi ngắn nhất.
Câu hỏi thường gặp
BFS có luôn tìm được đường đi ngắn nhất không?
Trên đồ thị không trọng số thì có — vì nó khám phá theo thứ tự khoảng cách tăng dần, lần đầu tới đích chính là qua một đường ngắn nhất. Trên đồ thị có trọng số thì chưa chắc, nên hãy dùng Dijkstra.
BFS khác DFS thế nào?
BFS dùng hàng đợi và mở rộng các nút gần nhất trước, đảm bảo đường đi ngắn nhất; DFS dùng ngăn xếp và đi sâu trước khi quay lui, nên không đảm bảo điều đó.