BFS và DFS là hai thuật toán duyệt đồ thị.
BFS (Breadth First Search - Tìm kiếm theo chiều rộng)
Thuật toán BFS duyệt đồ thị theo chuyển động chiều rộng và sử dụng hàng đợi (queue) để nhớ đỉnh tiếp theo khi gặp ngõ cụt trong bất kỳ lần lặp nào.
DFS (Depth First Search - Tìm kiếm theo chiều sâu)
Thuật toán DFS duyệt đồ thị theo chuyển động chiều sâu và sử dụng ngăn xếp (stack) để nhớ đỉnh tiếp theo khi gặp ngõ cụt.
Các khác biệt quan trọng:
| STT | Tiêu chí | BFS | DFS |
|---|---|---|---|
| 1 | Định nghĩa | Breadth First Search (Tìm kiếm chiều rộng) | Depth First Search (Tìm kiếm chiều sâu) |
| 2 | Cấu trúc dữ liệu | Dùng Queue (hàng đợi) để tìm đường ngắn nhất | Dùng Stack (ngăn xếp) để tìm đường ngắn nhất |
| 3 | Phù hợp khi | Đích gần nguồn (source) | Đích xa nguồn |
| 4 | Cây quyết định | Không phù hợp (xét tất cả hàng xóm) | Phù hợp hơn (sâu theo một quyết định) |
| 5 | Tốc độ | Chậm hơn DFS | Nhanh hơn BFS |
| 6 | Độ phức tạp thời gian | O(V+E) với V đỉnh, E cạnh | O(V+E) với V đỉnh, E cạnh |