Động lực

DFS duyệt một đồ thị bằng cách chọn một đường đi và đi theo đường đó xa nhất có thể, sau đó quay lui đến đỉnh cuối cùng còn láng giềng chưa được khám phá.

Tại sao nên học DFS?

• Nền tảng: DFS là nền tảng cho việc phát hiện chu trình, sắp xếp tô pô, tìm các thành phần liên thông và nhiều thuật toán khác.
• Đơn giản và tiết kiệm: DFS chạy trong thời gian O(V + E) bằng cách dùng ngăn xếp (hoặc đệ quy) và dấu đánh dấu đã thăm.
• Linh hoạt: cùng một cách duyệt có thể trả lời các câu hỏi như "hai đỉnh này có liên thông không?" và "đồ thị có bao nhiêu phần tách biệt?"

Để kết quả luôn dễ dự đoán, ta luôn thăm các đỉnh láng giềng theo thứ tự tăng dần.