Thuật toán tìm kiếm cây theo chiều sâu

Miêu tả thuật toán
Tìm kiếm ưu tiên chiều chiều sâu (tiếng Anh Depth-first search, viết tắt là DFS) là một thuật toán tìm kiếm trên đồ thị.


Thứ tự viếng thăm các đỉnh trong DFS,đi càng xa càng tốt, nếu không đi được nữa thì quay lại
Tư tưởng của thuật toán này là trong quá trình tìm các đỉnh của đồ thị để ghép vào cây ta luôn tìm các tìm các đỉnh càng xa gốc càng tốt. Áp dụng vào tìm cây bao trùm, thuật toán này được mô tả như sau. Gọi T là cây con sẽ được xây dưng
Chọn một đỉnh s bất kỳ của đồ thị làm gốc của cây T. Lúc này cây T chỉ có một đỉnh s là gốc của T., (s có mức 0) và chưa có cạnh nào. Tất cả các đỉnh trong G chưa được xét.
Lần lượt xét tất cả các đỉnh trong T có mức cao nhất nhất chưa xét xong. Mỗi lần xét đỉnh u: Tìm một cạnh nối đỉnh u với một đỉnh ngoài T.
Nếu không có các cạnh như vậy thì đỉnh u đã được xét xong. Ta quay về đỉnh đứng ngay trước đỉnh u.
Nếu có cạnh e=(u,v) nối u với v ngoài T thì bổ sung vào T cạnh e và đỉnh v. Nếu u có mức k thì đỉnh mới bổ sung v có mức k+1. Đỉnh mới bổ sung v chỉnh là đỉnh có mức cao nhất mới được bổ sung vào T.
Quá trình dừng lại khi tất cả các đỉnh nằm trong T đã được xét.
T là cây bao trùm cần tìm.
Ví dụ

Mã giả
Trong mã của giải thuật tìm kiếm theo chiều sâu ta cũng đưa vào các biến danh sách CORLOR(u) và PARENTS(u) trên tập các đỉnh. Sau khi khởi tạo ta dùng cách gọi đệ quy để tìm cây bao trùm của G(X,E)

Mã:

Procedure DFS ( G ){  /*Khởi tao*/     For each đỉnh of E do {                 COLOR[u] := WHITE                  PARENTS(u)=Null                  }    /* Tìm kiếm đệ quy*/        For each đỉnh u of E do          if if COLOR[u] = WHITE          then DFS-Visit (u)         Return PARENTS;     }      Procedure DFS-Visit(u) {         COLOR[u]:= GRAY   /*Bắt đầu xét u*/         for each v of Adj[u] do {              if COLOR[v] = WHITE                 then {                    PARENTS[v] := u                     DFS-Visit (v)                    }              }             COLOR[u]:=BLACK   /*Xét xong u*/         }

Giải thuật đệ quy trên đây dễ viết nhưng khó nhìn thấy ý nghĩa thực sự của giải thuật tìm kiếm theo chiều sâu. Trong nó có chứa một thao tác được gọi là thao tác quay lui: đi xa hết mức nếu có thể, nếu không thể đi được nữa thì lùi lại xét đỉnh ở bước trước (tức là đỉnh cha của nó).