- Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều sâu.
+ nếu gặp đường đi khác thì đi cho đến khi không đi tiếp được nữa
- Trong quá trình đi đến đỉnh khác, thuật toán sẽ lưu lại đỉnh cha vừa đi qua để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có thể xem được đường đi từ đỉnh Kết thúc đến đỉnh Bắt Đầu (có thể số lần đi không ít nhất, các bạn có thể tham khảo thuật toán
BFS).
- Sau đây là minh họa về thuật toán:
+ Hình 6 do không đi được nữa nên quay ngược về lại đỉnh bắt đầu.
Hình 6
Hình 7
+ Hình 9 sau khi đi qua đỉnh H, không thể đi tiếp được nữa nên tiến hành quay lại đến đỉnh xuất phát.
Hình 9
- Hình 11: khởi tạo các mảng và duyệt từng đỉnh theo chiều sâu
Hình 11
- Hình 13: Xem kết quả
Hình 13
Nguồn: http://www.studycoding.net/2014/03/thuat-toan-dfs-tim-kiem-theo-chieu-sau.html