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

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
    Trong quá trình thực hiện thuật toán, ở mỗi bước, ta có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị được sẽ được gán các nhãn. Nhãn của một đỉnh v gồm hai phần, [d[v], near[v]]. Trong đó, phần thứ nhất d[v] dùng để ghi nhận độ dài cạnh nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Phần thứ hai, near[v] ghi nhận đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả thông qua thủ tục sau:

void Prim(void){
 /*bước khởi tạo*/
 Chọn s là một đỉnh nào đó của đồ thị;
 VH = { s }; T = φ; d[s] = 0; near[s] = s;
 For(v∈V\VH) {
  D[v] = C[s, v]; near[v] = s;
 }
 /* Bước lặp */
 Stop = False;
 While(not stop) {
  Tìm u∈V\VH thoả mãn: d[u] = min{ d[v] với u∈V\VH };
  VH = VH∪{ u }; T = T ∪(u, near[u]);
  If(| VH | ) == n ) {
  H = <VH, T> là cây khung nhỏ nhất của đồ thị;
  Stop = TRUE;
  }Else{
   For(v ∈V\VH) {
    If(d[v] > C[u, v]) {
     D[v] = C[u, v];
     Near[v] = u;
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Prim tìm cây bao trùm nhỏ nhất được thực hiện như sau:

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

#include<iostream>
#include<conio.h>
using namespace std;
#define TRUE 1 
#define FALSE  0 
#define MAX  10000 
int a[100][100];//ma trận trọng số của đồ thị.
int n;//số đỉnh của đồ thị
int m;//số cạnh của đồ thị.
int sc;//số cạnh của cây khung nhỏ nhất.
int w;//Độ dài của cây khung nhỏ nhất.
int chuaxet[100];//mảng đánh dấu danh sách đỉnh đã thêm vào cây khung nhỏ nhất.
int cck[100][3];//danh sách cạnh của cây khung nhỏ nhất.
void nhap(void){
 int i, j, k;
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh: "<<n<<endl;
 cout<<"So canh: "<<m<<endl;
 //khỏi tạo ma trận trọng số của đồ thị a[i][j] = MAX.
 for (i = 1; i <= n; i++){
  chuaxet[i] = TRUE;//Gán nhãn cho các đỉnh.
  for (j = 1; j <= n; j++)
   a[i][j] = MAX;
 }

 //nhập danh sách cạnh.
 for (int p = 1; p <= m; p++){
  cin>>i>>j>>k;
  a[i][j] = k;
  a[j][i] = k;
 }
}
void PRIM(void){
 int k, top, min, l, t, u;
 int s[100];//mảng chứa các đỉnh của cây khung nhỏ nhất.
 sc = 0; w = 0; u = 1;
 top = 1;
 s[top] = u;// thêm đỉnh u bất kỳ vào mảng s[]
 chuaxet[u] = FALSE;
 while (sc<n - 1) {
  min = MAX;
  //tìm cạnh có độ dài nhỏ nhất với các đỉnh trong mảng s[].
  for (int i = 1; i <= top; i++){
   t = s[i];
   for (int j = 1; j <= n; j++){
    if (chuaxet[j] && min>a[t][j]){
     min = a[t][j];
     k = t;
     l = j;
    }
   }
  }
  sc++;
  w = w + min;
  //thêm vào danh sách cạnh của cây khung.
  cck[sc][1] = k;
  cck[sc][2] = l;
  chuaxet[l] = FALSE; 
  top++;
  s[top] = l;
 }
}
void Result(void){
 cout<<"Do dai ngan nhat:"<< w<<endl;
 cout<<"Cac canh cua cay khung nho nhat"<<endl;
 for (int i = 1; i <= sc; i++)
  cout<< cck[i][1]<<" "<< cck[i][2]<<endl;
}
void main(void){
 nhap(); 
 PRIM();
 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
1 3
3 5
5 4
4 6
3 2

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.