Lý thuyết cơ bản về DFS và BFS

1. DFS (Depth-First Search - Tìm kiếm theo chiều sâu)

• Bản chất: Đi "cắm đầu" đi sâu nhất có thể theo một hướng. Khi gặp ngõ cụt, mới quay ngược lại (backtrack) ngã rẽ gần nhất chưa khám phá để đi tiếp hướng khác.
• Hình ảnh ví dụ: Giống như đi thám hiểm một cái hang sâu, chọn một ngách và đi sâu mãi đến tận cùng rồi mới quay ra thử các ngách phụ khác.
• Cơ chế: Sử dụng Stack (Ngăn xếp) hoặc Đệ quy.
• Ứng dụng: Duyệt cây, tìm kiếm đường đi, kiểm tra chu trình, thành phần liên thông, quay lui.

2. BFS (Breadth-First Search - Tìm kiếm theo chiều rộng)

• Bản chất: Đi "loang" rộng ra từng lớp một. Đứng ở một điểm, khám phá hết hàng xóm gần nhất (khoảng cách 1 bước) rồi mới dịch chuyển sang các điểm xa hơn.
• Hình ảnh ví dụ: Thả viên sỏi xuống mặt hồ, gợn sóng lan rộng đều ra các phía theo hình tròn đồng tâm.
• Cơ chế: Sử dụng Queue (Hàng đợi - FIFO).
• Ứng dụng: Tìm đường đi ngắn nhất trên đồ thị không trọng số.

3. Bảng so sánh nhanh