[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây.
Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
2.  Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T trước đó;
3.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:

void  Kruskal(void){
 T = φ;
 While(| T | < (n - 1) and(E≠ φ)){
  Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
 E: = E\ {e};
  if (T ∪{ e }: không tạo nên chu trình)
   T = T ∪{ e };
 }
 if (| T | <n - 1)
  Đồ thị không liên thông;
} 

Khối lượng tính toán nhiều nhất cảu thuật toán chính là ở bước sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài các cạnh để bổ xung vào cây khung. Đối với đồ thị cỡ m cạnh thì  cần phải thực hiện cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, ta không cần sắp xếp toàn bộ mà chỉ cần xét phần trên cảu dãy đó. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp vun đống (Heap sort).
Trong thuật toán Kruskal việc lựa chọn cạnh để bổ xung đòi hỏi phải có một thủ tục hiệu quả đế kiểm tra tập cạnh T ∪ { e } có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc cùng một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo thành chu trình khi và chỉ khi nó phải nối 2 cây khác nhau trong T. Một trong những phương pháp hiệu quả để thực hiện việc kiểm tra này là phân hoạch các đỉnh của đồ thị thành các tập con không giao nhau. Chẳng hạn với đồ thị sau.

Tìm cây khung nhỏ nhất với thuật toán Kruskal

Ta có tập con có 6 tập con 1 phần tử: {1},{2},{3},{4},{5},{6}. Sau khi bổ xung cạnh có độ dài nhỏ nhất {3,5} ta có các tập con : {1},{2},{3,5},{4},{6}. Tiếp theo ta thêm cạnh {4,6} ta được các tập con {1},{2},{3,5},{4,6}. Tiếp theo ta thêm canh {4,5} ta được các tập con {1},{2},{3,5,4,6}. Cạnh có độ dài tiếp theo là {5,6} nhưng do hai đầu của nó thuộc cùng một tập con {3,5,4,6} nên cạnh {5,6} không được chọn.
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50 
#define TRUE 1 
#define FALSE  0 
int n, m, minl, connect;
int dau[500], cuoi[500], w[500];//mảng chứa đỉnh đầu, cuối và độ dài các cạnh của đồ thị.
int daut[50], cuoit[50], father[50];
void Init(void){
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh do thi: "<< n <<endl;
 cout<<"So canh do thi:" << m <<endl;
 //nhập danh sách kề
 for (int i = 1; i <= m; i++){
  cin>>dau[i]>>cuoi[i]>>w[i];
 }
}
void Heap(int First, int Last){
 int j, k, t1, t2, t3;
 j = First;
 while (j <= (Last / 2)){
  if ((2 * j) < Last && w[2 * j + 1] < w[2 * j])
   k = 2 * j + 1;
  else
   k = 2 * j;
  if (w[k] < w[j]){
   t1 = dau[j];
   t2 = cuoi[j];
   t3 = w[j];
   dau[j] = dau[k];
   cuoi[j] = cuoi[k];
   w[j] = w[k];
   dau[k] = t1;
   cuoi[k] = t2;
   w[k] = t3;
   j = k;
  }
  else j = Last;
 }
}
int Find(int i){
 int tro = i;
 while (father[tro] > 0)
  tro = father[tro];
 return(tro);
}
void Union(int i, int j){
 int x = father[i] + father[j];
 if (father[i] > father[j]) {
  father[i] = j;
  father[j] = x;
 }
 else {
  father[j] = i;
  father[i] = x;
 }
}
void Krusal(void){
 int last, u, v, r1, r2, ncanh, ndinh;
 for (int i = 1; i <= n; i++)
  father[i] = -1;
 //sử dụng thuật toán vun đống để sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài.
 for (int i = m / 2; i > 0; i--)
  Heap(i, m);

 last = m; ncanh = 0; ndinh = 0; minl = 0; connect = TRUE;
 //Lựa chọn cạnh bổ xung vào cây khung.
 while (ndinh < n - 1 && ncanh < m){
  ncanh = ncanh + 1;
  u = dau[1];
  v = cuoi[1];
  //tìm gốc của phân hoạch 1.
  r1 = Find(u);
  //tìm gốc của phân hoạch 2.
  r2 = Find(v);
  if (r1 != r2) {//nếu hai gốc khác nhau thì cạnh đang xét có thể thêm được vào đồ thị.
   ndinh = ndinh + 1;
   Union(r1, r2);
   daut[ndinh] = u;
   cuoit[ndinh] = v;
   minl = minl + w[1];
  }
  dau[1] = dau[last];
  cuoi[1] = cuoi[last];
  w[1] = w[last];
  last = last - 1;
  Heap(1, last);
 }
 if (ndinh != n - 1) connect = FALSE;
}
void Result(void){
 cout<<"Do dai cay khung nho nhat:"<< minl<<endl;
 cout<<"Cac canh cua cay khung nho nhat:"<<endl;
 for (int i = 1; i < n; i++)
  cout<< daut[i]<<" "<<cuoit[i]<<endl;
}
void main(void){
 Init();
 Krusal();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
3 5
4 6
4 5
1 3
2 3

Bài tập ứng dùng bạn có thể xem thêm tại đây

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.