Tìm kiếm theo chiều sâu

Bách khoa toàn thư mở Wikipedia

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.

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 hàng đợi LIFO.

Độ phức tạp không gian của DFS thấp hơn của BFS (tìm kiếm ưu tiên 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|)).

[sửa] Ví dụ

Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là: A, B, D, F, E, C, G.

Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D. Từ D không thê tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm BF, từ F đến thăm E. Từ E vì A đã viếng thăm nên ta quay lại F, rồi quay lại B. Tại B vì tất cả các khả năng từ B đã xem xét nên ta quay lại A. Từ A, quá trình tiếp tục với các đỉnh C và G.