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

Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta sẽ trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung của bài toán.
     Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = {1,2,..., n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số thực c(e), gọi là độ dài của nó. Giả xử H = (V, T) là cây khung của đồ thị. Ta gọi độ dài c(H) của cây khung H là tổng độ dài của các cạnh của nó:

c(H) = SUM(c(e)) ; e thuộc T

Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.
Bài toán xây dựng hệ thống đường sắt: Giả sử ta muốn xây dựng hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ thành phố nào đến bất kỳ một trong các thành phố còn lại. Mặt khác trên quan điểm kinh tế đòi hỏi là chi phí về  xây dựng hệ thống đường phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án tối ưu phải là cây. Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các cạnh chính là chi phí xây dựng đường ray nối hai thành phố tương ứng.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy vi tính đánh số từ 1 đến n. Biết chi phí nối máy I với máy j là c[i,j] , i,j = 1,2…,n. Hãy tìm cách nối mạng là nhỏ nhất.
Trong đó thuật toán Kruskal và Thuật toán Prim là hai thuật toán phổ biến và nổi tiếng để tìm cây khung nhỏ nhất.

1. Thuật toán Kruskal
2. Thuật toán Prim

[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