Pohon rentang minimum (minimum spanning tree) dalam C++

Pohon rentang minimum merupakan istilah dalam teori graf (Inggris: minimum spanning tree). Pohon rentang adalah sebuah pohon yang mencakup semua titik (node) pada sebuah graf terhubung. Bobot pohon rentang merupakan jumlah bobot sisi-sisi pembentuk (cabang) pohon rentang. Pohon rentang minimum adalah pohon rentang dari graf, dengan bobot minimal.

Definisi yang lebih formal : Pohon rentang minimum adalah pohon rentang dari graf sedemikian sehingga semua pohon rentang lain memiliki bobot lebih besar atau sama dengan pohon rentang minimum.

#include<iostream>
#include <cstdlib>
//#include<conio>

using namespace std;
class prims
{
private:
int n;                      //jumlah titik
int graph_edge[250][4];    //sisi dari graf
int g;                      // nilai sisi dari graf
int tree_edge[250][4];    //sisi dari pohon
int t;                    //nilai sisi dari pohon
int s; //source node
//mengatur partisi menjadi 2 bagian
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";
cout<<"Program Minimum Spanning Tree Algoritma Prim\n";
cout<<"--------------------------------------------\n";
cout<<"Input banyak graf yang akan dibentuk  :";cin>>n;
g=0;
cout<<"Input bobot tiap node :\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";//nilai sisi dari graf
int w;
cin>>w;
if(w!=0)
{
g++;
graph_edge[g][1]=i;
graph_edge[g][2]=j;
graph_edge[g][3]=w;
}
}
}

cout<<"\n\nGraf yang terbentuk :\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)
{
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; //inisialisasi titik T1 dimulai dari 1
t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //perulangan untuk titik T2
cout<<"\n-----Algoritma Prim-----\n\n";
while(g!=0 && t!=n-1)
{
// menemukan sisi terendah dari graf
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           //jika u dan v diset yang berbeda
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;
}
}
}
                 
cout<<"Sisi yang terdapat pada graf :";
cout<<" < "<<u<<" , "<<v<<" > "<<endl;
for(int l=p;l<g;l++)
{
graph_edge[l][1]=graph_edge[l+1][1];
graph_edge[l][2]=graph_edge[l+1][2];
graph_edge[l][3]=graph_edge[l+1][3];
}
g--;

t++;
tree_edge[t][1]=u;
tree_edge[t][2]=v;
tree_edge[t][3]=w;

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];
t2--;

// 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<<"Grafnya adalah ::\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<<"\nSisi yang terpilih ::\n";
for(int i=1;i<=t;i++)
cout<<" < "<<tree_edge[i][1]<<" , "<<tree_edge[i][2]<<" > ::"<<tree_edge[i][3]<<endl;
}

int main(int argc, char *argv[])
{
prims obj;
obj.input();
obj.algorithm();
obj.output();

system("PAUSE");
return EXIT_SUCCESS;
}