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.
Ví dụ:
Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh , đ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à: .
Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh , vì chưa được thăm nên theo cạnh ta thăm , tiếp tục theo cạnh tới viếng thăm . Từ không thê tiếp tục đi xa hơn, ta quay lại . Từ , theo đến thăm , từ đến thăm . Từ vì A đã viếng thăm nên ta quay lại , rồi quay lại . Tại vì tất cả các khả năng từ đã xem xét nên ta quay lại . Từ , quá trình tiếp tục với các đỉnh và .
Bài toán đặt ra là:
Cho đơn đồ thị vô hướng gồm đỉnh và cạnh, các đỉnh được đánh số từ tới và các cạnh được đánh số từ tới .
Bằng thuật toán tìm kiếm theo chiều sâu, hãy đưa ra danh sách các đỉnh theo thứ tự tìm kiếm. Biết rằng: Đỉnh nào có chỉ số bé hơn sẽ được ưu tiên thăm trước.
Dữ liệu vào:
Dòng đầu ghi hai số nguyên ;
dòng tiếp theo, mỗi dòng gồm hai số nguyên mô tả một cạnh (nối giữa đỉnh và đỉnh ).
Dữ liệu ra:
Gồm dòng, mỗi dòng gồm một số ghi số hiệu đỉnh theo thứ tự duyệt DFS.
