Thuật toán Prim - thuật toán tìm cây khung nhỏ nhất bằng C/C++

Thuật toán Prim - thuật toán tìm cây khung nhỏ nhất bằng C/C++

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.

Ứng dụng: >>> Bài toán xây dựng đường sắt được cài đặt theo thuật toán Prim và C/C++

Thuật toán Kruskal

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:

#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ề

6  9
1  2  33
1  3  17
2  4  20
2  3  18
3  4  16
3  5  4
4  5  9
4  6  8
5  6  14

Output của chương trình

Số đỉnh: 6

Số cạnh: 9

Độ dài ngắn nhất: 56

Các cạnh của cây khung nhỏ nhất

1  3
3  5
5  4
4  6
3  2

Lưu ý: Các bạn có thể xây dựng thêm phần đồ họa thay cho chạy bằng tay

Việc sử dụng đồ họa trong C/C++ các bạn có thể tìm hiểu thêm trên Google

Bạn thấy bài viết này như thế nào?: 
Average: 9.7 (14 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Bình luận (0)

 

Add Comment

Plain text

  • No HTML tags allowed.
  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Tự động ngắt dòng và đoạn văn.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Hiển thị Bootstrap Components sử dụng Views Bootstrap

Hiển thị Bootstrap Components sử dụng Views Bootstrap

Bootstrap is a mobile first front-end framework that allows a developer to build websites quickly. The framework comes with a lot of reusable CSS styles, components and jQuery plugins.

Bitcoin đang 'nóng' nhất kể từ ngày lên giá 20.000 USD

Theo Bloomberg Bitcoin đang 'nóng' nhất kể từ ngày lên giá 20.000 USD hồi tháng 12.2017

Theo Bloomberg, có một tín hiệu mà những người yêu tiền mã hóa nên chú ý: Bitcoin hiện ở mức đắt đỏ nhất kể từ trước ngày “bong bóng vỡ”, khi giá cả từ 20.000 USD lao dốc không phanh.

Giới thiệu REST Easy phần 2: Sub Property Boogaloo

Giới thiệu REST Easy phần 2: Sub Property Boogaloo

Hello again, RESTful friends. Welcome to episode II, The RESTful strikes back

Tomdesgin.vn

 

Drupal Services