Pengertian Algoritma Prim dan Program C++

Algoritma Prim

Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung

Langkah-langkahnya adalah sebagai berikut:

1. buat sebuah pohon yang terdiri dari satu node, dipilih secara acak dari graf
2. buat sebuah himpunan yang berisi semua cabang di graf
3. loop sampai semua cabang di dalam himpunan menghubungkan dua node di pohon
4. hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu node di pohon dengan satu node di luar pohon
5. hubungkan cabang tersebut ke pohon

Algoritma Kruskal

Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T. Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit. 

Contoh program C++ spaning Tree dengan metode Algoritma Prim :

#include <cstdlib>
#include <iostream>

using namespace std;

class prims
{
private:
int n; //no of nodes =>tidak ada node
int graph_edge[250][4]; //edges in the graph =>tepi dalam grafik
int g; //no of edges in the graph => tidak ada dari tepi dalam grafik
int tree_edge[250][4]; //edges in the tree =>  tepi di pohon
int t; //no of edges in the tree => tidak ada tepi di pohon
int s; //source node =>node sumber
//Partition the graph in to two sets => Partisi grafik ke dua set
int T1[50],t1; // Set 1
int T2[50],t2; // Set 2
public:
void input();
int findset(int);
void algorithm();
void output();
};
void prims::input()
{
cout<<"*************************************************\n"
<<" program implements the prims algorithm \n"
<<"*************************************************\n";
cout<<"Enter the no. of nodes in the undirected weighted graph/"<<endl;
cout<<"Masukkan no tersebut. node dalam graf berbobot berarah ::";
cin>>n;
g=0;
cout<<"Enter the weights for the following edges "<<endl;
cout<<" Masukkan bobot untuk tepi berikut ::\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";  //untuk menampilkan batas (i,j)
int w;
cin>>w;
if(w!=0)
{
g++;
graph_edge[g][1]=i;  //tepi graf 1
graph_edge[g][2]=j;  //tepi graf 2
graph_edge[g][3]=w;  //tepi graf 3
}
}
}
// print the graph edges
cout<<"\n\nThe edges in the given graph are"<<endl;
cout<<"=>Tepi dalam grafik yang diberikan::\n";
for(int i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}
int prims::findset(int x)  //hasil dari proses algoritma prim
{
for(int i=1;i<=t1;i++)
if(x==T1[i])
return 1;
for(int i=1;i<=t2;i++)
if(x==T2[i])
return 2;
return -1;
}
void prims::algorithm()
{
t=0;
t1=1;
T1[1]=1; //The source node
t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //The reamining nodes
cout<<"\n*****The algorithm starts*****\n\n";
while(g!=0 && t!=n-1)
{
// Find the least cost edge
int min=9999;
int p;
int u,v,w;
for(i=1;i<=g;i++)
{
bool flag1=false,flag2=false;
//if u and v are in different sets
if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))
{
if(min>graph_edge[i][3])
{
min=graph_edge[i][3];
u=graph_edge[i][1];
v=graph_edge[i][2];
w=graph_edge[i][3];
p=i;
}
}
}
//break if there is no such edge
cout<<"The edge included in the tree is "<<endl;
cout<<"=>Tepi termasuk dalam pohon adalah::";
cout<<" < "<<u<<" , "<<v<<" > "<<endl;
//delete the edge from graph edges
for(int l=p;l<g;l++)
{
graph_edge[l][1]=graph_edge[l+1][1];  //hasil batas tepi graf ke 1
graph_edge[l][2]=graph_edge[l+1][2];  //hasil batas tepi graf ke 2
graph_edge[l][3]=graph_edge[l+1][3];  //hasil batas tepi graf ke 3
}
g--;
//add the edge to the tree
t++;
tree_edge[t][1]=u;  //tepi pohon ke 1
tree_edge[t][2]=v;  //tepi pohon ke 2
tree_edge[t][3]=w;  //tepi pohon ke 3
//Alter the set partitions
t1++;
int m;
if(findset(v)==2)
{
T1[t1]=v;
m=v;
}
else if(findset(u)==2)
{
T1[t1]=u;
m=u;
}
int x;
for(x=1;T2[x]!=m;x++);
for(;x<t2;x++)
T2[x]=T2[x+1];
// Print the sets
int k;
cout<<"NOW\nT1 :: ";
for(k=1;k<=t1;k++)
cout<<T1[k]<<' ';
cout<<endl;
cout<<"T2 :: ";
for(k=1;k<=t2;k++)
cout<<T2[k]<<' ';
cout<<endl;
cout<<"\nThe graph edges are"<<endl;
cout<<"=> ujung grafik nya ::\n";
for(i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
cout<<endl<<endl;
}
}
void prims::output()
{
cout<<"\n\nThe selected edges are "<<endl;
cout<<"=> Tepi yang dipilih adalah ::\n";
for(int i=1;i<=t;i++)
cout<<" < "<<tree_edge[i][1]
<<" , "<<tree_edge[i][2]
<<" > ::"<<tree_edge[i][3]<<endl;
}
int main()
{
prims obj;
obj.input();
obj.algorithm();
obj.output();

    system("PAUSE");
    return EXIT_SUCCESS;
} 

Output :