DFS (Depth-first search) là một thuật toán tìm kiếm ưu tiên chiều chiều sâu

Tư tưởng ca thut toán này là trong quá trình tìm các đnh ca đ th đ ghép vào cây ta luôn tìm các tìm các đnh càng xa gc càng tt. Áp dng vào tìm cây bao trùm, thut toán này được mô t như sau. Gi T là cây con s được xây dưng

  1. 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.
  2. 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.
    1. 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.
    2. 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.
    3. Quá trình dừng lại khi tất cả các đỉnh nằm trong T đã được xét.
  3. 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)

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ó).

Giải thuật không đệ quy

Theo nguyên tắc đị xa nhất có thể, giải thuật không đệ quy tìm cây bao trùm theo chiều sâu cần đến một cấu trúc ngăn xếp S (Stack) để lưu trữ các đỉnh theo thứ tự đưa vào cây. Khi khới tạo ta cho một đỉnh bất kỳ váo ngăn xếp S.

Ở mỗi bước ta lấy đỉnh u nằm cuối Stack ra để xét. Nếu trong danh sách các đỉnh kề với u không còn đỉnh nào chưa nằm trong cây T (tất cả chúng đã xét xong hoặc nằm trong Stack) thì đỉnh u đã xét xong, nếu có một đỉnh không nằm trong Stack và chưa xét thì chó nó vào Stack. Quá trình chấm dứt khi Stack là rỗng.

Procedure DFS(G,r){

Var
Stack S, list COLOR(u), PARENTS(u)

/*Khởi tạo: Tất cả các đinh chưa xét */

For each’ v of E do {

COLOR(u):=WHITE

PARENTS(u):=NULL

}

/* Cho đỉnh đầu tiên vào Stack*/

COLOR(r):=GRAY


Push(S,r)


While’ S khác rỗng do (

u= End(S); /* Xét phần tử mằm sau cùng trong Stack*/


Find:=False ;


For each v of Adj(u) do {


If COLOR(v)=WHITE then {

PARENT(v):=u

COLOR(v):=GRAY


Push(S,v) /*Bổ sung v vào cuối ngăn xếp*/

Breack

find=TRUE

}


if not
Find
then {

COLOR(u)=BLACK

Pos(S,u) /*Lấy u khỏi Stack */

}

}

}

 

Trong giải thuật này mỗi lần xét một đỉnh cuối trong ngăn xếp, ta không vội vã đưa nó ra khỏi ngăn xếp. Nó chỉ được xét xong và đưa khỏi ngăn xếp khi tất cả các đỉnh kề với nó đã được đưa vào cây (nằm chờ trong ngăn xếp hoặc đã xét xong). Mỗi lần một đỉnh đưa khỏi ngăn xếp ta quay lại xét phần tử đứng trước nó trong ngăn xếp là ta đã thức hiện một thao tác “quay lui“. Như vậy đỉnh đưa vào đầu tiên bao giờ cũng là đỉnh cuối cùng ra khỏi ngăn xếp.

Thay cho thao tác tìm đỉnh trắng trong danh sách kề với đỉnh u, ta cũng có thể lấy ngay phần tử đầu tiên v trong danh sách kề Adj(u) (nếu nó khác rỗng) vào ngăn xếp và xóa v khỏi danh sách kề. Khi đó toàn bộ các đỉnh trong danh sách kề của u đều chưa được xét.

Ta có:

Procedure DFS(G,r){

Var
Stack S, list COLOR(u), PARENTS(u)

/*Khởi tạo: Tất cả các đinh chưa xét */

For each’ v of E do {

COLOR(u):=WHITE

PARENTS(u):=NULL

}

/* Cho đỉnh đầu tiên vào Stack*/

COLOR(r):=GRAY


Push(S,r)

/*lần lượt xét các đỉnh*/


While’ S khác rỗng do (

u= End(S); /* Xét phần tử mằm sau cùng trong Stack*/


If Adj(u) khác rỗng then

v=Adj(u)(1)

Delete(Adj(u),v) /*Xóa (tạm thời) v khỏi danh sách kề của u*/

PARENT(v):=u


Push(S,v) /*Bổ sung v vào cuối ngăn xếp*/


else {

COLOR(u)=BLACK


Pos(S,u) /*Lấy u khỏi Stack */

}

}

}


 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: