Cây bao trùm

Miêu tả thuật toán

Thứ tự viếng thăm các đỉnh trong BFS, gần trước, xa sau

Tư tưởng của thuật toán này là trước tiên tìm trên tất các đỉnh gần với đỉnh xuất phát nhất trong khả năng có thể. Áp dụng vào tìm cây bao trùm, thuật toán được mô tả như sau

Gọi 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 thấp nhất chưa xét xong. Mỗi lần xét đỉnh u:

• Tìm tất cả các 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.
• Nếu có e=(u,v) nối u với v nằm ngoài T thì bổ sung vào T tất cả các cạnh e=(u,v) và đỉnh v như vậy . Nếu u có mức k thì các đỉnh mới bổ sung có mức k+1. Khi đó đỉnh u đã được xét xong.
• 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ụ

Với sự mô tả trên đây có thể tìm cây bao trùm dễ dàng trên các đồ thị có số các đỉnh và cạnh tương đối nhỏ.

Mã giả

Để xây dựng giải thuật trên máy tính cần làm rõ các cấu trúc dữ liệu biểu diễn đồ thị cũng như quá trình xét các đỉnh và các cạnh. Giả sử đồ thị G cho bởi các danh sách các cạnh kề với từng đỉnh. Danh sách này thường được ký hiệu là Adj[u] đối với danh scáh các cạnh kề đỉnh u. Để phân biệt các đỉnh chưa nằm trong T, các đỉnh trong T đã xét xong và chưa xét, ta hình dung một quá trình tô màu các đỉnh: Đỉnh mới bổ sung vào T thì tô màu xám (GRAY), đỉnh trong T đã xét xong thi tô màu đen (BLACK), các đỉnh chưa nằm trong T thi tô mầu trắng (WHITE). Ta còn muốn xác định các cạnh nào nằm trên cây. Xem T như một cây có gốc, trừ gốc, mỗi cạnh trong cây nối một đỉnh với cha của nó, vì vậy ta dùng một hàm Parent(u) để xác định các cạnh được đưa vào cây T. Vì thế, khi khởi tạo ta có các biến danh sách COLOR(u) và PARENTS(u). Theo nguyên tắc xét đỉnh gần gốc nhất, các đỉnh gia nhập cây sớm sẽ được xét trươc. Để "theo dõi" chặt chẽ thứ tự các đỉnh được đưa vào T ta dùng một cấu trúc hàng đợi Q (Queue).

Procedure BFS(G,r) {
    Var list COLOR(u),PARENTS(u),Queue Q 
    /* Khởi tạo */
    For each u of E do {
    GRAY(u)=WHITE
    PARENTS(u)=Null
    }
    Push(Q,r) /*Đẩy đỉnh đầu tiên vào hàng đợi*/
    

/*Xét các đỉnh*/
    While Q <> rỗng do {
    u = Pop(Q);/*Lấy đỉnh đầu hàng đợi Q ra để xét*/
    COLOR(s)=GRAY
    For each v of Adj(u) 
    {
    if COLOR(v)=WHITE then {
    COLOR(v)=GRAY
    PARENTS(v)=u
    Push(Q,v) /*đẩy đỉnh v vào hàng đợi*/
    } 
    COLOR(u)=BLACK
    } 
    }
    Return PARENTS
    
    

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

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.

• 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.

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 */
    }
    }
    }