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.2 (5 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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.
1 + 1 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Dịch vụ diệt muỗi tận gốc tại nhà tháng 03 năm 2016

Dịch vụ diệt muỗi tận gốc tại nhà tháng 03 năm 2016

Thông thường dịch vụ diệt muỗi sẽ được bảo hành trong 03 tháng tính từ ngày thực hiện phun thuốc.

Bài 4 : Học sinh lập trình Scratch tạo thêm nhân vật thứ hai

Bài 4 : Học sinh lập trình Scratch tạo thêm nhân vật thứ hai

Trong cửa sổ Scratch, bạn hãy mở tập tin chương trình mà bạn đã lưu sau khi thực hiện trò chơi đơn giản “Dơi bắt chuột”. Nhìn lại những gì đã làm

LG "bắt tay" Google

LG bắt tay Google

Gần đây, nhiều nguồn tin cho rằng, LG hiện đang tìm cách để dự phần vào sản phẩm TV của Google.

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer