อัลกอริธึมของพริม เป็นวิธีการโลภที่ใช้เพื่อค้นหาแผนภูมิการขยายขั้นต่ำสำหรับกราฟที่ไม่ระบุทิศทางที่ถ่วงน้ำหนัก
กราฟถ่วงน้ำหนัก เป็นกราฟที่มีขอบทั้งหมดมีค่าน้ำหนัก
กราฟไม่มีทิศทาง เป็นกราฟชนิดพิเศษที่ขอบทั้งหมดเป็นแบบสองทิศทาง
ต้นไม้ทอดข้ามขั้นต่ำ เป็นเซตย่อยที่มีขอบและจุดยอดทั้งหมด แต่ไม่มีวงรอบ และมีน้ำหนักขอบรวมน้อยที่สุดที่เป็นไปได้
ในบทความนี้ เราจะเรียนรู้เกี่ยวกับอัลกอริทึมของ prim เพื่อค้นหา spanning tree ขั้นต่ำ โดยปกติ อัลกอริทึมจะใช้สองอาร์เรย์ แต่ในโซลูชันนี้ เราจะใช้เพียงอาร์เรย์เดียว
โปรแกรมแสดงการใช้งานอัลกอริธึมของพริม
ตัวอย่าง
#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;
} ผลลัพธ์
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
