Thuật toán của Prim là một phương pháp tham lam được sử dụng để tìm cây bao trùm tối thiểu cho một đồ thị vô hướng có trọng số nhất định.
Biểu đồ có trọng số là một đồ thị có tất cả các cạnh có giá trị trọng số.
Biểu đồ vô hướng là một loại biểu đồ đặc biệt, trong đó tất cả các cạnh đều có hai hướng.
Cây bao trùm tối thiểu là tập hợ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ẽ tìm hiểu về thuật toán prim để tìm cây bao trùm tối thiểu. Thông thường, thuật toán sử dụng hai mảng nhưng trong giải pháp này, chúng tôi sẽ chỉ sử dụng một mảng.
Chương trình hiển thị việc triển khai thuật toán của linh trưởng.
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<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
MSTcost += min;
inMST[b] = inMST[a] = true;
}
}
cout<<"Cost of Minimum spanning tree ="<<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<<"The Minimum spanning tree for the given tree is :\n";
printMinSpanningTree(cost);
return 0;
} Đầu ra
The Minimum spanning tree for the given tree is : Edge 0 : (0 , 1 ) : cost = 12 Edge 1 : (1 , 3 ) : cost = 8 Edge 2 : (1 , 2 ) : cost = 11 Edge 3 : (1 , 4 ) : cost = 12 Cost of Minimum spanning tree =43