Cây bao trùm nhỏ nhất

Bách khoa toàn thư mở Wikipedia

Cây bao trùm nhỏ nhất của đồ thị mặt phẳng.
Phóng lớn
Cây bao trùm nhỏ nhất của đồ thị mặt phẳng.

Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài toán tối ưu có nhiều ứng dụng trong thực tế. Nó có thể là bài toán tìm hệ thống liên thông với chi phí nhỏ nhất, hoặc ngược lại, vói lợi nhuân lớn nhất. Hai thuật toán tìm cây bao trùm nhỏ nhất và lớn nhất thường được nhắc đến là thuật toán Prim và thuật toán Krusskal.

Mục lục

[sửa] Bài toán

Cho G=(X,E) là một đồ thị liên thông. Ngoài ra, một hàm trọng số W(e) nhận các giá trị thực, xác định trên tập các cạnh E của G. Cả hai thuật toán Prim và Krusskal đều dựa trên tư tưởng của các giải thuật tham lam: Ở mỗi bước của thuật toán ta chọn và bổ xung vào cây cạnh có trọng số nhỏ nhất có thể.

[sửa] Giải thuật Prim

Giải thuật Prim dựa trên cấu trúc của giải thuật tìm cây bao trùm theo chiều rộng hoặc chiều sâu, chỉ thay đổi về tiêu chuẩn chọn đỉnh sẽ bổ xung vào cây ở tưng bước.

[sửa] Vài nét R. C. Prim

Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà toán học và khoa học máy tính Mỹ. Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông nhận bằng Ph.D. về toán học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi nhà toán học Vojtěch Jarník và do Prim hoàn thiện vào năm 1957.

[sửa] Mô tả

Gọi T là cây bao trùm sẽ xây dựng

  1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào.
  2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc.
  3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T.
  4. Quay lại 2.

[sửa] Giả mã

Giải thuật trình bày Prim ở trên dễ dàng thực hiện khi ta quan sát một đồ thị được biểu diễn trên mặt phẳng với một số ít đỉnh. Tuy nhiên để cài đặt thành một chương trình chạy trên máy tính cũng cần phân tích thêm một số điểm.

Liệu có thể sử dụng một hàng đợi (queue) giống như trong giải thuật tìm cây bao trùm theo chiều sâu không? Có. Nhưng điều khác biệt là ta sẽ sử dụng một hàng đợi có ưu tiên, tiêu chuẩn ưu tiên ở đây là cạnh nối đỉnh sẽ được bổ xung vào T là nhỏ nhất. Một cấu trúc thuận lợi cho hàng đợi có ưu tiên là cấu trúc đống (heap) như đã sử dụng trong giải thuật sắp xếp vun đống hoặc giải thuật xây dựng mã Huffman. Giả sử G=(X,E) là đồ thị liên thông, Ajd(u) , u\in X là danh sách đỉnh kề của đỉnh u. L(e) là hàm trọng số xác đinh với moi cạnh e\in E Chúng ta cúng dùng một hàm. Trong đoạn mã sau ta dung hàm COLOR(u) để tô màu các đỉnh của G bằng các màu WHITE, GRAY, BLACK để chỉ các trạng thái chưa xét, đang xét và đã xét xong của mỗi đỉnh, hàm PARENTS(u) chỉ đỉnh cha của đỉnh u trong cây, hàm DISTAN(u,T) chỉ trọng số nhỏ nhất của các cạnh nối từ đỉnh u ngoài T đến các đỉnh trong T. Ta cũng sử dụng một cấu trúc HEAP làm hàng đợi ưu tiên chứa các đỉnh đang chờ xét.

Ở bước khởi tạo, một đỉnh r bất kỳ được đưa vao Heap. Số các phần tử của đống là n=1. Cho đến khi hàng đợi Heap còn khác rỗng ta thực hiện các bước sau: lấy đỉnh u nằm ở gốc Heap ra để đưa vào cây. Đối với đỉnh u mới được bổ xung vào cây ta duyệt qua tất cả các đỉnh v thuộc danh sách kề với nó. Nếu đỉnh v chưa thuôch T và không nằm trong đống ta chèn v vào đống, nếu đỉnh v đã nằm trong đống đợi ta tính lại khoảng cách từ v của nó với tập các đỉnh đã nằm trong T, và vun lại đống. Sau khi tất cả các đỉnh v \in Ajd(u) đã duyệt qua bằng cách ấy thì thì đỉnh u đã được duyệt xong và được đưa vào cây.

 Procedure Prim (G, r, W(e)) {
 Var list COLOR(u), PARENTS(u), DISTAN(u),Heap H
   
  For each u of  E  {
         COLOR(u)= WHITE
         PARENTS(u)=Null
         DISTAN(u)= M
         }
         H(1)=r
         n=1
         DISTAN(r)=0
  While n> 0 do
       u=H(1)
       n=n-1
       Color(u)=BLACK
       For each v of Ajd(u) {
       if (Color(v)=WHITE)
          or ((Color(v)=GRAY) and  (DISTAN(v)<W(u,v)   
          then
                {
                  COLOR(v)=GRAY
                  PARENTS(v)=u
                  DISTAN(v)=W(u,v)    
                  if Color(v)=WHITE  then InsertHeap(H,v)
                  else UpHeap(H,HeapIndex(v))
                } 
         }      
       }
 

[sửa] Các thao tác trên Heap

  • Trong đoạn mã trên có sử dụng hàm InsertHeap(H,v) để chèn đỉnh v vào đống H, hàm UpHeap(H,v) để sắp xếp lại đống H (vun lại đống) khi thay giá trị DISTAN(v) bằng giá trị nhỏ hơn.
  • Trong các thủ tục về Heap, ta tổ chức Heap như một mảng H(1..n) trong đó mỗi phần tử trong nó là các đỉnh của G được sắp xếp sao cho DISTAN(H(i))\le DISTAN(H(2*i)) (nếu 2*i \le n) và DISTAN(H(i))\le DISTAN(H(2*i+1)) (nếu 2*i+1\le n).
  • Vì Heap chứa các đỉnh nên ta thêm một mảng HeapIndex(v) để xác định vị trí của đỉnh v trong Heap.
  • Thao tác InsertHeap thêm một phần tử vào cuối Heap và điều chỉnh lại vị trí các phần tử sao cho nó vẫn là Heap nhờ thao tác UpHeap(H,n).
  • Thao tác UpHeap(k) điều chỉnh lại vị trí của phần tử v nằm tại vị trí thứ k của Heap khi giá trị DISTAN(v) thay bằng giá trị nhỏ hơn. Rõ ràng khi đó chỉ cần so sánh DISTAN của v với DISTAN của đỉnh cha của trong Heap.
Procedure InsertHeap(H,v){
   n:=n+1
   Heap(n):=v
   IndexHeap(v)=n
   UpHeap(H,n) 
   }
Procedure UpHeap (H,k){
   i:= Lshift(k,1) /*Chia đôi lấy phần nguyên*/
   While (k>0) and DISTAN(H(k))<DISTAN(H(i)) {
        Swap(H(k),H(i)) /*Đổi chỗ H(k) H(i)*/
        k:=i
        i:=LShift(k,1) /*Chia đôi lấy phần nguyên*/
        }
    }

[sửa] Giải thuật Kruskal

Giải thuật Kruskal không dựa trên tư tưởng của các thuật toán tìm kiếm theo chiều rộng hoặc chiều sâu. Trong các thuật toán này, tại từng bước của quá trình xây dựng T luôn là một cây, chỉ có điều kiện về số đỉnh của T phải đến bước cuối cùng mới thỏa mãn. Còn trong thuật toán Kruskal, trong quá trình xây dựng T có thể chưa là cây, nó chỉ thỏa mãn điều kiện không có chu trình.

[sửa] Mô tả

Giả sử G có n đỉnh. Gọi T là cây bao trùm sẽ xây dựng.

  1. Chọn cạnh của G có trọng số nhỏ nhất cho vào T (cùng với hai đỉnh của nó). Khi đó T là một cây có một cạnh và hai đỉnh.
  2. Nếu T đã gồm đúng n-1 cạnh của G thì T là cây bao trùm cần tìm. Kết thúc.
  3. Nếu G còn chưa đủ n-1 cạnh , thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn các cạnh của G chưa thuộc T. Trong các cạnh của G chưa thuộc T có các cạnh không tạo ra chu trình với các cạnh đã có trong T , Chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ xung (cùng với các đỉnh chưa thuộc T của nó) vào T.
  4. Quay lại 2.

[sửa] Giả mã

[sửa] Phân tích

  • Khi lập trình cài đặt giải thuật Kruskal có hai điểm mấu chốt cần chú ý:
  1. Trong mỗi lần lặp ta chọn cạnh có trọng số nhỏ nhất đưa vào T.
  2. Cạnh được chọn đưa vào T phải không tạo thành chu trình với các cạnh đã có trong T.
  • Vấn đề thứ nhất được giải quyết gần giống như trong giải thuật Prim là tạo một hàng đợi có ưu tiên trên danh sách các cạnh. Tuy nhiên có thể ngay từ đầu sắp xếp các cạnh theo thứ tự tăng dần của trọng số.

Để giải quyết vần đề thứ hai, ta quay lại chú ý rằng, khác với giải thuật Prim, tại mỗi bước của giải thuật Kruskal, tập các đỉnh và các cạnh đã được đưa vào T chưa là cây mà chỉ thỏa mã tính không chu trình. Như vậy tại mỗi bước T là một rừng, T = T_1 \cup T_2 \cup . ..\cup T_k.

  • Bây giờ xét một cạnh e = (u,v) của G chưa nằm trong T có 3 khả năng xảy ra:
  1. Cả u,v chưa thuộc T. Khi đó nếu bổ xung e vào T thì không có chu trình, nhưng chính cạnh e tạo thành một cây con mới.
  2. Một đỉnh chẳng hạn u thuộc T, còn đỉnh kia v không thuộc T. Việc bổ xung cạnh e và đỉnh v vào T (vào cây con chứa đỉnh u) không tạo ra chu trình.
  3. Cả u,v đều nằm trong T. Khi đó
    1. Nếu u,v nằm trong cùng một cây con Tk ta không thể bổ xung canh e vào T.
    2. Nếu u,v nằm trong hai cây con khác nhau thì có thể bổ xung cạnh e vào T (hai đỉnh u, v đã nằm trong T không cần bổ xung, sau khi bổ xung hai cây con sẽ hợp lại thành một cây.

[sửa] Tổ chức dữ liệu

  • Giả sử G=(X,E)là đồ thị vô hướng cho bằng danh sách kề Ajd(u), u \in X. Hàm trọng số W(u,v) xác định trên các cạnh (u,v)\in E. Với mỗi cạnh e=(u,v) ký hiệu e.x u, e.y=v là hai đỉnh liên thuộc với cạnh e.
  • Các biến sau được đưa vào
    • k biểu diễn số cây con được tạo ra trong T;
    • Tree(u), xác định với mọi u \in X biểu diễn thứ tự của cây con mà u được đưa vào trong T. Khi khởi tạo Tree(u)=0 với mọi u\in X. Khi kết thúc nếu G liên thông Tree(u)=1 với mọi u\in X
    • Hàm Root(k) lưu trữ đỉnh gôc của cây con thứ k
    • Hàng đợi Q của các cạnh xếp theo thứ tự trọng số từ nhỏ đến lớn.
    • Hàm PARENTS(u) xác định trên X, biểu diễn đỉnh cha của đỉnh u.

[sửa]

 Procedure Kruskal  (G)
/*Khởi tạo, và cho một cạnh có trọng số nhỏ nhất vào T*/
 Q =Sort(E)
 For each  u of X do Tree(u):=0;     
 k = 1
 m = |E|
 e = Q(1)
 Tree(e.x):=1
 Tree(e.y):=1
 PARENTS(e.y):=e.x
 PARENTS(e.x):=Null
 Root(1)=e.x
 For  i=2 to m do {
     e = Q(i)
     If Tree[e.x]=0 and Tree[e.y]=0 then {
          /* Thêm cây thứ k+1 u*/
          k:=k+1
          Tree(e.x):=k
          Tree(e.y):=k
          PARENTS(e.y):=e.x
          PARENTS(e.x):=Null
     }
     If Tree[e.x] # Tree[e.y] then {
         If Tree(e.x)>Tree(e.y) then {
              u:=e.x
              v:=e.y
              }
         else {  
              u:=e.e
              v:=e.x
              }
         If Tree(v)>0 then {
              Tree(v):=Tree(u)
              Union(Tree(u),Tree(v)) /* Ghép cây chứa v vào cây chứa u*/
         'else {/* Ghép đỉnh v vào cây chứa u*/                 
              Tree(v):=Tree(u)
              PARENTS(v):=u 
          }
        /* nếu Tree(e.x)=Tree(e.y)>0 thì không làm gì và loại cạnh đó đi*/
     }      
  {      

     

Ghi chú:

  • Thủ tục Union(Tree(u),Tree(v)),ghép cây chứa v vào cây chứa u thực hiện các việc sau:
    • Nếu v không là gốc của cây chứa nó thì định lại hướng các cạnh của cây ấy để v trở thành gốc.
    • Từ gốc, duyệt các đỉnh của cây chứa đỉnh v, gán lại giá trị Tree(v) của tất cả các đỉnh trong cây chứa v theo Tree(u).
  • Khi kết thúc thuật toán vẫn còn nhiều hơn một cây thì đồ thị là không liên thông.