Duyệt theo chiều sâu (DFS - Depth-First Search) | Quỳnh Chi

speed Tốc độ:

parkNguyên lý hoạt động

DFS luôn ưu tiên đi sâu hết mức có thể dọc theo một nhánh trước khi buộc phải lùi lại (Backtrack) khi đụng tường ngõ cụt.

 Khác với BFS, thuật toán DFS KHÔNG đảm bảo tìm được đường đi ngắn nhất ở lần chạm đích đầu tiên! Nó chỉ chứng minh được "có tồn tại đường tới đích hay không". 

Nó được thiết kế tự nhiên trên Cấu trúc dữ liệu Stack (Ngăn xếp - LIFO) hoặc kỹ thuật Gọi đệ quy.

account_treeỨng dụng thực tế

sports_esportsTrí tuệ Nhân tạo: Rất nổi tiếng trong việc dùng vét cạn giải Mê cung hoặc giải đố Sudoku (kết hợp Backtracking).
account_treeMạng lưới: Rà soát Cây thư mục (File System) trên Windows/Linux.