Tìm kiếm theo chiều sâu
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ể ...
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 ngăn xếp 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|).
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à:
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.
Một cách tự nhiên, kết quả của giải thuật tìm kiếm theo chiều sâu là một cây phủ qua tất cả các đỉnh được duyệt của đồ thị.
Duyệt các đỉnh
Có thể dùng giải thuật này để tạo một danh sách tuyến tính các đỉnh của một đồ thị (hoặc cây). Có ba cách hiện thực phương pháp này:
Duyệt tiền thứ tự (preordering): tạo ra một danh sách mà trong đó các định xuất hiện theo đúng trật tự nó được thăm đến khi chạy thuật toán. Đây chính là biểu diễn tự nhiên của quá trình thực hiện giải thuật tìm kiếm theo chiều sâu. Một biểu thức ở dạng tiền thứ tự được gọi là kí pháp tiền tố.
Duyệt hậu thứ tự (postordering): tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo thứ tự của lần duyệt đến sau cùng khi thực hiện giải thuật. Một lần suyệt hậu thứ tự một cây biểu thức sẽ cho ra một kí pháp hậu tố.
Duyệt đảo hậu thứ tự (reverse postordering): kết quả của cách duyệt này là sự đảo ngược lại thứ tự trong kết quả duyệt hậu thứ tự. Thông thường, khi duyệt cây, cách này cho ra cùng kết quả với duyệt tiền thứ tự, nhưng xét tổng quát, khi duyệt một đồ thị, tiền thứ tự và đảo hậu thứ tự cho ra kết quả khác nhau. Với các đồ thị có hướng và không có vòng, cách duyệt đảo hậu thứ tự cho ra một trật tự tô-pô của đồ thị đó.
Ứng dụng
Nhiều giải thuật sử dụng tìm kiếm theo chiều sâu:
Xác định các thành phần liên thông của đồ thị
Sắp xếp tô-pô cho đồ thị
Xác định các thành phần liên thông mạnh của đồ thị có hướng
Kiểm tra một đồ thị có phải là đồ thị phẳng hay không
