Tổng quan
Depth-First Search (DFS) khám phá đồ thị bằng cách đi sâu nhất có thể theo một nhánh trước khi quay lui để thử nhánh khác. Nó chọn một hướng và đi theo cho đến khi gặp ngõ cụt hoặc đích, rồi lùi về ngã rẽ chưa khám phá gần nhất.
DFS dễ cài đặt bằng đệ quy hoặc một ngăn xếp tường minh, nhưng trên lưới nó đi lang thang xa điểm xuất phát và không đảm bảo đường đi tìm được là ngắn nhất.
Tìm kiếm theo chiều sâu (DFS) hoạt động thế nào?
- Đẩy nút xuất phát vào ngăn xếp (hoặc bắt đầu lời gọi đệ quy) và đánh dấu đã thăm.
- Lấy nút trên đỉnh ngăn xếp và chọn một hàng xóm chưa thăm.
- Đi sâu vào hàng xóm đó, đánh dấu đã thăm và ghi lại nút cha.
- Khi một nút không còn hàng xóm chưa thăm, quay lui về nút trước và thử nhánh khác, cho đến khi tới đích.
Khi nào nên dùng?
- Sinh mê cung và kiểm tra đơn giản xem có tồn tại đường đi giữa hai ô hay không.
- Các bài toán đồ thị như phát hiện chu trình, sắp xếp tô-pô và tìm thành phần liên thông.
- Tránh dùng khi cần đường đi ngắn nhất — lộ trình của nó thường dài hơn cần thiết nhiều.
Phân tích độ phức tạp
Giống BFS, DFS chạm mỗi đỉnh và cạnh một lần nên chạy trong thời gian O(V + E). Bộ nhớ là O(V) cho tập đã thăm và ngăn xếp đệ quy hoặc tường minh, với độ sâu có thể bằng đường đi dài nhất. DFS không phải là thuật toán đường đi ngắn nhất.
Câu hỏi thường gặp
Vì sao DFS không tìm được đường đi ngắn nhất?
DFS bám theo một nhánh đến tận cùng trước khi xét lựa chọn khác, nên có thể tới đích bằng một lộ trình dài và ngoằn ngoèo trong khi một đường ngắn hơn vẫn chưa được khám phá. BFS hoặc Dijkstra mới đảm bảo đường đi ngắn nhất.
Khi nào DFS là lựa chọn tốt hơn?
Khi bạn chỉ cần biết có tồn tại đường đi hay không, muốn khám phá hoặc sinh mê cung, hoặc giải các bài toán cấu trúc đồ thị như phát hiện chu trình, nơi việc đi sâu chính là điều bạn cần.