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.

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.

Xem thêm Thuật toán tìm cây bao trùm

Mục lục

1 Bài toán
2 Giải thuật Prim
3 Giải thuật Kruskal
- 3.1 Mô tả
- 3.2 Giả mã

[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à Kruskal đề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ổ sung 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ổ sung 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

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.
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.
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.
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ổ sung 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$ . Trong đoạn mã sau ta dùng 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ổ sung 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] Một chương trình đầy đủ bằng ngôn ngữ Pascal

 program 
 Prim_Algorithm;
 uses dos,crt;
 const max=150;
 type
 filename=string[12];
 var
 TrongSo: array[1..max,1..max] of integer;
 DinhKe: array[1..max] of integer;
 CanhKe: array[1..max] of integer;{}
 n, DodaiCayKhung: integer;
 i,j: integer;
 fname: filename;
 ch: char;
 h,m,s, hund:word;
 procedure PrintMatrix;
 Begin
    (*In ma tran ra *)
         Writeln('-------------------------------------------------------');
         Writeln('Ma tran trong so, Khong co canh noi thi trong so = MaxInt');
         for i:=1 to n do
         Begin
            For j:=1 to n do
               if TrongSo[i,j]=Maxint then write('    0',' ')
                    else write(TrongSo[i,j]:5,' ');
            Writeln;
         End;
         Writeln('-------------------------------------------------------');
 End;
 procedure 
 ReadInputFile(fname: filename);
 var
 i,j: integer;
 f: text;
 begin
 assign(f,fname);
 reset(f);
 readln(f,n);
 for i:=1 to n do
   begin
     for j:=1 to n do
       begin
         read(f,TrongSo[i,j]);
         if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
       end;
     readln(f);
   end;
 close(f);
  PrintMatrix;
  end;
  procedure Prim;
 var
 v,i,k: integer;
 min: integer;
 begin
 for v:=2 to n do
   begin
     DinhKe[v]:=1;
     CanhKe[v]:=TrongSo[1,v];
   end;
 for i:=2 to n do 
   begin
     min:=MaxInt;
     for k:=2 to n do
       if (CanhKe[k]>=0) and (CanhKe[k]<min) then
         begin
           min:=CanhKe[k];  (
           v:=k;
         end;
     CanhKe[v]:=-1; 
     for k:=2 to n do
       if (TrongSo[v,k]<CanhKe[k]) and (TrongSo[v,k]>0)  then
         begin
           CanhKe[k]:=TrongSo[v,k];
           DinhKe[k]:=v;   
         end;
   end;
 end;
 procedure 
 WriteOutputFile;
 var
 i: integer;
 f: text;
 begin
 assign(f,'prim.out');
 rewrite(f);
 Writeln(f,'-------------------------------------------------------');
         Writeln(f,'Ma tran trong so, Khong co canh noi thi trong so = MaxInt');
         for i:=1 to n do
         Begin
            For j:=1 to n do
               if TrongSo[i,j]=Maxint then write(f,'    0',' ')
                    else write(f,TrongSo[i,j]:5,' ');
            Writeln(f,);
         End;
         Writeln(f,'-------------------------------------------------------');
 DodaiCayKhung:=0;
 writeln(f,'Cay khung nho nhat gom cac canh:');
 for i:=2 to n do
   begin
     write(f,'(',i,',',DinhKe[i],') ');
     DodaiCayKhung:=DodaiCayKhung+TrongSo[i,DinhKe[i]];
   end;
 writeln(f);
 writeln(f,'Length: ',DodaiCayKhung);
 close(f);
  end;
  begin
  repeat
  clrscr;
  writeln('THUAT TOAN PRIM TIM CAY KHUNG NHO NHAT');
  writeln('           DUNG MA TRAN KE');
  writeln('---------------------------------------');
  writeln('  Hay bam phim chuc nang:');
  Writeln;
  writeln('    K(eyboard). Chay chuong trinh - Du lieu nhap tu ban phim.');
  Writeln;
  writeln('    F(ile). Chay chuong trinh - Du lieu lay tu File.');
  Writeln;
  writeln('    R(andom). Chay chuong trinh - Du lieu Random.');
  Writeln;
  writeln('    Q(uit). Thoat khoi chuong trinh.');
  Writeln;
  ch:=ReadKey;
  case UpCase(ch) of
    'F':
       begin
         write('    Hay nhap ten tep du lieu:'); readln(fname);
         ReadInputFile(fname);
         gettime(h,m,s,hund);
         Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
         Prim;
         gettime(h,m,s,hund);
         Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
         WriteOutputFile;
         write('Cac canh cua cay khung be nhat:');
         for i:=2 to n do write('(',i,',',DinhKe[i],')');
         writeln;
         writeln('Gia cua cay khung : ',DodaiCayKhung);
         writeln('***************************************');
         writeln('Nhan phim Enter de tiep tuc.');
         readln;
       end;
     'R':
       begin
         write('Hay nhap so dinh cua do thi:'); readln(n);
         for i:=1 to n do TrongSo[i,i]:=0; 
         for i:=1 to n-1 do
         For j:=i+1 to n do TrongSo[i,j]:=random(100); 
         for i:=2 to n do
         For j:=1 to i-1 do TrongSo[i,j]:=TrongSo[j,i]; 
         PrintMatrix;
         for i:=1 to n do
        for j:=1 to n do
         if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
         gettime(h,m,s,hund);
         Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
         Prim;
         gettime(h,m,s,hund);
         Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
         write('Cac canh cua cay khung be nhat:');
         for i:=2 to n do write('(',i,',',DinhKe[i],')');
         WriteOutputFile;
         Writeln;
         writeln('Gia cua cay khung : ',DodaiCayKhung);
         writeln;
         writeln('***************************************');
         writeln('Nhan phim Enter de tiep tuc.');
         readln;
       end;
     'K':
       begin
         write('Hay nhap so dinh cua do thi:'); readln(n);
         for i:=1 to n do TrongSo[i,i]:=0; 
         for i:=1 to n-1 do
         For j:=i+1 to n do
            Begin
                Write('a[',i,j,']=');
                readln(TrongSo[i,j]);  (* Nua tren *)
            End;
         for i:=2 to n do
         For j:=1 to i-1 do TrongSo[i,j]:=TrongSo[j,i]; 
         PrintMatrix;
         for i:=1 to n do
         for j:=1 to n do
         if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
         gettime(h,m,s,hund);
         Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
         Prim;
         gettime(h,m,s,hund);
         Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
         write('Cac canh cua cay khung be nhat:');
         for i:=2 to n do write('(',i,',',DinhKe[i],')');
         WriteOutputFile;
         writeln;
         writeln('Gia cua cay khung : ',DodaiCayKhung);
         writeln('***************************************');
         writeln('Nhan phim Enter de tiep tuc.');
         readln;
       end;
   end;
   until 
   UpCase(ch)='Q';
   end.

[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ị $D I S T A N (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)) ≤ DISTAN(H(2*i)) (nếu 2*i ≤n) và DISTAN(H(i)) ≤ DISTAN(H(2*i+1)) (nếu 2*i+1 ≤ n).
Vì Heap chứa các đỉnh nên ta thêm một mảng $H e a p I n d e x (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ị $D I S T A N (v)$ thay bằng giá trị nhỏ hơn. Rõ ràng khi đó chỉ cần so sánh $D I S T A N$ của v với $D I S T A N$ 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 liên thông có n đỉnh. Gọi T là cây bao trùm sẽ xây dựng.

Khởi tạo: T lúc đầu là một đồ thị rỗng.
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.
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ổ sung (cùng với các đỉnh chưa thuộc T của nó) vào T.
Quay lại 2.

Một vài tác giả có cách trình bày khác của giải thuật Kruskal, tuy bản chất quá trình là giống nhau

Khởi tạo: T lúc đầu gồm tất cả các đỉnh của G và chưa có cạnh nào,như vây T lúc đầu là một rừng n cây,mỗi cây gồm đúng một đỉnh.
Nếu T chỉ gồm một cây thì dừng
Nếu T gồm nhiều hơn một cây, chọn cạnh nhỏ nhất của G có hai đầu mút thuộc hai cây khác nhau bổ sung vào T, khi đó hai cây được hợp thành một cây.
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ú ý:

Trong mỗi lần lặp ta chọn cạnh có trọng số nhỏ nhất đưa vào T.
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:

Cả $u, v$ chưa thuộc T. Khi đó nếu bổ sung $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.
Một đỉnh chẳng hạn $u$ thuộc T, còn đỉnh kia $v$ không thuộc T. Việc bổ sung 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.
Cả u,v đều nằm trong T. Khi đó
1. Nếu $u, v$ nằm trong cùng một cây con $T k$ ta không thể bổ sung canh $e$ vào T.
2. Nếu $u, v$ nằm trong hai cây con khác nhau thì có thể bổ sung cạnh e vào T (hai đỉnh u, v đã nằm trong T không cần bổ sung, sau khi bổ sung 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=(V,E)là đồ thị vô hướng n đỉnh, cho bằng danh sách kề Ajd(u), $u \in X$ . Các đỉnh của G được đánh số từ 1 đến n, nghiã là V=V[1..n];Ta cũng kí hiệu Index(u) là chỉ số của đỉnh u trong mảng V.

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
- Hàng đợi Q của các cạnh xếp theo thứ tự trọng số từ nhỏ đến lớn.
- Với mỗi cây con, hàm PARENTS(u) xác định trên V, biểu diễn chỉ số của đỉnh cha của đỉnh u trong một cây. Riêng đỉnh gốc u của mỗi cây hàm PARENTS(u)lưu trữ số đỉnh trong cây với dấu âm.

[sửa] Mã

 Procedure Kruskal  (G)
 T = V;
 Q =Sort(E)
/* Tạo n cây, mỗi cây gồm một đỉnh*/
 For each  u of X do Parent(u):=-1;     
 m = |E|
 For  j:=1 to m do {
     u:=NodeStart(Q(j)); V:=NodeEnd(Q(j))        
     If Find_tree(u)<>Find_tree(V) then 
           T:=T U Q[j];
           Union(u,v;)

Ghi chú:

Thủ tục Find_set(u) tìm đỉnh gốc của cây chứa đỉnh u. (xem cây biểu diễn tập hợp).
Thủ tục Union(u,v),ghép cây chứa v vào cây chứa u (xem cây biểu diễn tập hợp).

See also ebooksgratis.com: no banners, no cookies, totally FREE.

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

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

Mục lục

[sửa] Bài toán

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

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

[sửa] Mô tả

[sửa] Giả mã

[sửa] Một chương trình đầy đủ bằng ngôn ngữ Pascal

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

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

[sửa] Mô tả

[sửa] Giả mã

[sửa] Phân tích

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

[sửa] Mã

Views

Chuyển hướng

Tìm kiếm

Ngôn ngữ khác