![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/langvi-640px-Depth-first-tree.svg.png&w=640&q=50)
Tìm kiếm theo chiều sâu
From Wikipedia, the free encyclopedia
Tìm kiếm ưu tiên chiều sâu hay tìm kiếm theo chiều sâu (tiếng Anh: Depth-first search - DFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh.
Thuật toán tìm kiếm theo chiều sâu | |
![]() | |
Ví dụ về thứ tự duyệt theo chiều sâu | |
Phân loại | Thuật toán tìm kiếm |
Cấu trúc dữ liệu | Đồ thị |
Độ phức tạp thời gian | O(|V|+|E|) với đơn đồ thị, không duyệt vòng
|
Độ phức tạp không gian | O(|V|) nếu duyệt toàn bộ đồ thị, mỗi đỉnh qua đúng một lần |
Thông thường, DFS là một dạng tìm kiếm thông tin không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vào một ngăn xếp LIFO.
Độ phức tạp không gian của DFS thấp hơn của BFS (tìm kiếm theo chiều rộng). Độ phức tạp thời gian của hai thuật toán là tương đương nhau và bằng O(|V| + |E|).