Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

Tư tưởng của thuật toán Kruskal (Joseph Kruskal, 1956):

Cho đồ thị G = (V, E), có n đỉnh và m cạnh. Gọi T* là cây khung tối thiểu cần xây dựng.

(a) V* = V; // Tập đỉnh của cây khung

(b) T* = Æ; // T* là tập cạnh của cây khung

(c) Temp = E; // tập cạnh tạm thời

(d) while (Temp ¹ Æ)

(d1) Tìm một cạnh e = (u, v) mà có trọng số là nhỏ nhất trong tập Temp;

(d2) Xoá cạnh e này ra khỏi Temp;

(d3) Nếu khi thêm cạnh e này vào cây khung T tức là T* = T* È (u, v) mà không tạo thành chu trình thì thêm cạnh e này vào T*;

 

Như vậy, đã thực hiện xong thuật toán, kết quả cho cây khung nhỏ nhất của đồ thị hình 4.21 là T, gồm có các cạnh chọn được tô đậm trong hình 4.24 với tổng trọng số bằng 28.

Tuy nhiên, nếu sắp xếp các cạnh trước theo thứ tự trọng số tăng dần trước, với thuật toán sắp xếp tốt, thì ta thấy ngay độ phức tạp của thuật toán chỉ còn là O(mlogm).

(a) V* = V;

(b) T* = Æ;

(c) Temp = E;

(d) Sắp xếp cách cạnh trong Temp tăng dần theo trọng số;

(e) while (Temp ¹ Æ)

    (e1) Tìm cạnh e = (u,v) mà có trọng số là nhỏ
     nhất trong Temp;

    (e2) Xoá cạnh e này ra khỏi Temp;

    (e3) Nếu khi thêm cạnh e này vào cây khung T,
     tức là T* = T* È (u,v) mà không tạo thành
     chu trình thì thêm cạnh e này vào T*;

 

Rõ ràng là, thuật toán Kruskal tốt đối với những đồ thị thưa thớt, nhiều đỉnh, nhưng ít cạnh (vẫn liên thông).

Việc kết nạp một cạnh nào đó mà có trọng số nhỏ nhất trong các cạnh chưa được kết nạp, dễ nhận thấy là chỉ cần có trọng số nhỏ nhất và không tạo thành chu trình khi thêm vào tập cạnh của
cây khung.

Nhận thấy rằng, khi cài đặt chương trình tìm cây khung nhỏ nhất bằng thuật toán Kruskal, việc kết nạp các cạnh vào cây khung không cần điều kiện cho cạnh được kết nạp là phải liên thông với cây khung.

Từ định nghĩa cây là đồ thị vô hướng liên thông không có chu trình; đồ thị không có chu trình được gọi là rừng. Như vậy, rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. Trong ví dụ trên, ta thấy ban đầu cây chưa có cạnh nào được kết nạp và khi kết nạp các cạnh thì có thể tạo các thành phần liên thông không có chu trình, vì thế mỗi thành phần liên thông là một cây và tập hợp các thành phần liên thông không có chu trình tạo thành một rừng. Do vậy, trong chương trình sẽ xây dựng một rừng tên là TD, ban đầu rừng này gồm có n cây, trong quá trình kết nạp thì mỗi cây sẽ được thêm các đỉnh vào hoặc loại bỏ các đỉnh để cuối cùng tạo được một rừng gồm một cây. Trong hình 4.24 chỉ còn có một cây gồm các đỉnh liên thông với nhau mà không tạo thành chu trình.

Cho đồ thị như trong hình 4.21 là G = (V, E), V = {1, 2, 3, 4, 5, 6} có số đỉnh là 6 (n = 6), E = {(1, 2, 5), (1, 3, 10), (1, 4, 9), (2, 4, 4), (3, 4, 13 ), (3, 5, 14), (4, 5, 7), (4, 6, 8), (5, 6, 2) } có số cạnh là
9 (m = 9).

Trước khi áp dụng thuật toán Kruskal để tìm cây khung tối thiểu được cải tiến ở trên, ta có nhận xét:

- Việc tìm cây khung tối thiểu của thuật toán là đi tìm các cạnh thoả mãn hai điều kiện là trọng số của cạnh được chọn phải là nhỏ nhất và khi thêm vào cây khung không tạo thành chu trình trong cây khung. Mỗi khi tìm được một cạnh thì cũng tìm được đỉnh của cạnh ấy để thêm vào tập đỉnh của cây khung, ký hiệu tập đỉnh của cây khung là V*.

- Thực chất của việc tìm các đỉnh của cây khung được tiến hành đồng thời trong quá trình tìm cạnh của cây khung; nếu tìm được cây khung thì tập đỉnh của đồ thị và tập đỉnh của cây khung là một, cho nên thực hiện gán tập đỉnh V* := V = {1, 2, 3, 4, 5, 6} trước khi đi tìm các cạnh.

- Trước khi tìm cây khung, các đỉnh trong cây khung chưa được nối với nhau như trong đồ thị G, như vậy, tập V* đang chứa n đỉnh, n đỉnh này tạo thành n thành phần liên thông. Ta có thể tạo ra n tập đỉnh; mỗi tập gồm một đỉnh từ n đỉnh này. Vì thế, V* sẽ được viết là V* = {{1}, {2}, {3}, {4}, {5}, {6}}; V* gồm có n cây, n cây này sẽ là một rừng nếu ta kết nối được các cây này lại với nhau. Theo định nghĩa, cây là một rừng có n đỉnh, do đó thuật toán chỉ cần tìm ra một tập gồm tất cả các đỉnh của đồ thị (tạo thành một thành phần liên thông).

- Nếu một cạnh được chọn thì kiểm tra đỉnh đầu và đỉnh cuối của cạnh được chọn là tập nào. Giả sử đỉnh đầu thuộc tập A, đỉnh cuối thuộc tập B, ta thực hiện hợp nhất tập A và B vào tập A; sau khi hợp nhất thì tất cả các đỉnh thuộc tập B sẽ được chuyển hết vào tập A (tức là tập B trở thành rỗng). Quá trình hợp nhất các tập với nhau sẽ kết thúc khi tập V* chỉ còn một tập gồm n phần tử, các tập còn lại là rỗng.

Từ những nhận xét trên, ta có thể thực hiện tìm cây khung nhỏ nhất của đồ thị G theo thuật toán Kruskal vừa cải tiến. Trong bảng dưới đây, quy ước cột "Được chọn" dùng để đánh dấu cạnh được chọn, tức là cạnh đó được đánh dấu là 1, ngược lại đánh dấu là 0.

· Bước 1. Khởi tạo

- Khởi tạo tập đỉnh:

  V* = {{1}, {2}, {3}, {4}, {5}, {6} };

  E* = {}; //tập rỗng

  Trọng số = 0; Số cạnh = 0;

  //số cạnh của cây khung nhỏ nhất

Tệp tin:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 100
#define FALSE 0
#define TRUE  1

typedef struct Canh{
    char d,c;
    int  trongso;
};

typedef struct Node{
    char d;// ten dinh
    Node *next;
};
    Node *td[MAX];// Khai bao mot danh sach cac tap dinh
    Canh ds[MAX];   // khai bao danh sach canh cua do thi
    int n,m;        // n:so dinh cua do thi, m: so canh cua do thi
// cac ham thanh phan

void menu();
void makenulltd();// Khoi tao danh sach tap dinh la rong
void nhapdothitutep(char tt[30]); // nhap do thi moi tu tep tin
void kruscal();   // tim cay khung do thi

void main()
{    int stop = FALSE; char ch;

     do{   clrscr();
       menu();
       ch=getch();
       switch(ch)
       {
        case '1': nhapdothitutep("dt.txt");
              getch(); break;
        case '2': kruscal(); getch(); break;

       case 'E','e': stop=TRUE; break;
       }
       }while (!stop);
}

void kruscal()
{  int  k,i,j,trongso;
   char Dinh[MAX];
   int  Cay[MAX]; // Mang nay luu chi so cua canh duoc chon

   Dinh[1]:='a';
   Dinh[2]:='b'; Dinh[3]:='c'; Dinh[4]:='d'; Dinh[5]:='e';
   Dinh[6]:='f'; Dinh[7]:='g'; Dinh[8]:='h'; Dinh[9]:='k';

     for i:=1 to n do TD[i]:=[];
     Sapxep(DC,m);
     tr:=0; k:=0;
     for i:=1 to n do TD[i] := [ Dinh[i] ]; { khoi tao n tap dinh la n rung }
     for i:=1 to m do
     begin
    if not chutrinh(i)  then
       begin
          tr:= tr + DC[i].tr;
          k:= k + 1;
          Cay[k]:=i;
          Hopnhat(i);
       end;
     end;
      writeln;writeln;writeln('Thuat toan Kruscal...');writeln;
      writeln('Cay khung T:', k ,' canh'); writeln;
      writeln('Danh sach cac canh');writeln; writeln;
      write('T* = { ');
      i:=1;
      while (i <= k) do
      begin
    for j:=1 to m do
if ( cay[i]=j ) then  write(#32:1,'(',DC[cay[i]].d,',',DC[cay[i]].c,
',',DC[cay[i]].tr,')');
      i:=i+1;
      end;writeln(' };');
      writeln;writeln;
      writeln('Trong so la :',tr);
end;

}
void menu()
{
    printf("\nXAY DUNG CAY KHUNG NHO NHAT\n");
    printf("1. Nhap danh sach canh\n");
    printf("2. Tim cay khung bang thuat toan Kruskal\n");
    printf("E. Ket thuc chuong trinh:");

}
void makenulltd()
{ int i;
  for (i=1;i<=n;i++) td[i]=NULL;
}

void nhapdothitutep( char tt[30])
{  FILE *fp;  char tentep[20];
   int n,i,j; int tr;
   char d[1],c[1];// dinh doc duoc
   strcpy(tentep,tt);
   if ((fp = fopen(tentep,"rt")) == NULL){
       fprintf(stderr, "Khong mo duoc tep tin %s",tentep);
       return;
   }
   printf("\n\nDANH SACH CANH CUA DO THI\n\n");
   fscanf(fp,"%d%d\n",&n,&m);
   for(j=1;j<=m;j++){
         fscanf(fp,"%s %s %d",&d,&c,&tr);
         printf("(%s,%s,%d)\n",d,c,tr);
      }
   fclose(fp);
   printf("\nDa doc xong tep tin...");
}

Tham khảo: Nguyễn Trường Xuân và các tác giả, Lý thuyết đồ thị và ứng dụng, nxb Giáo dục Việt Nan, 2017. 

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI