Thuật toán Prim là một phương pháp tham lam được sử dụng để tìm cây khung nhỏ nhất cho một đồ thị vô hướng có trọng số cho trước.
Đồ thị có trọng số là đồ thị mà tất cả các cạnh đều có giá trị trọng số.
Đồ thị vô hướng là một loại đặc biệt của đồ thị mà tất cả các cạnh đều hai chiều.
Cây khung nhỏ nhất là một tập con chứa tất cả các cạnh và đỉnh nhưng không có chu trình và có tổng trọng số cạnh nhỏ nhất có thể.
Trong bài viết này, chúng ta sẽ học về thuật toán Prim để tìm cây khung nhỏ nhất. Thường thì thuật toán sử dụng hai mảng nhưng trong giải pháp này, chúng ta sẽ chỉ sử dụng một.
Chương trình minh họa triển khai thuật toán Prim:
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
if (u == v)
return false;
if (inMST[u] == false && inMST[v] == false)
return false;
else if (inMST[u] == true && inMST[v] == true)
return false;
return true;
}
void printMinSpanningTree(int cost[][V]){
vector<bool> inMST(V, false);
inMST[0] = true;
int edgeNo = 0, MSTcost = 0;
while (edgeNo < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (cost[i][j] < min) {
if (createsMST(i, j, inMST)) {
min = cost[i][j];
a = i;
b = j;
}
}
}
}
if (a != -1 && b != -1) {
cout<<"Cạnh "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : chi phí = "<<min<<endl;
MSTcost += min;
inMST[b] = inMST[a] = true;
}
}
cout<<"Chi phí cây khung nhỏ nhất ="<<MSTcost;
}
int main() {
int cost[][V] = {
{ INT_MAX, 12, INT_MAX, 25, INT_MAX },
{ 12, INT_MAX, 11, 8, 12 },
{ INT_MAX, 11, INT_MAX, INT_MAX, 17 },
{ 25, 8, INT_MAX, INT_MAX, 15 },
{ INT_MAX, 12, 17, 15, INT_MAX },
};
cout<<"Cây khung nhỏ nhất cho cây cho trước là :\n";
printMinSpanningTree(cost);
return 0;
}
Kết quả
Cây khung nhỏ nhất cho cây cho trước là : Cạnh 0 : (0 , 1 ) : chi phí = 12 Cạnh 1 : (1 , 3 ) : chi phí = 8 Cạnh 2 : (1 , 2 ) : chi phí = 11 Cạnh 3 : (1 , 4 ) : chi phí = 12 Chi phí cây khung nhỏ nhất =43