/////////////COMMON//////////////////////
#include<iostream.h>
#include<stdio.h>
#define MAXINT 999
int N;
int i,j;
/////////////KRUSKAL/////////////////////
int kruskal();
int find (int i);
void merge (int p, int q);
int equal (int p, int q);
int U[120],M=0,W[100][100];
int E[120][103]; //me /* complete set of edges */
int F[120][103]; //me /* set of edges in min. span. tree */
int num_edges = 0; /* num of edges in m s tree */
int next_edge = 0; /* next edge not yet considered */
int weight = 0; /* minimal spanning tree weight */
int a, b, c, k;
//////////////PRIMS//////////////////////
int prims();
void read_from_user(void);
int findmin(void);
int x,l,cost[120][120],tr[120][102],mincost=0,nears[20];
/////////////KRUSKAL/////////////////////
int kruskal()
{
cout<<"\n\nKruskal ALgorithm : \n\n";
//read_from_user();
/* initialize set of edges */
k = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (j > i)
{ E[k][0] = i; /* first vertex of edge */
E[k][1] = j; /* second vertex of edge */
E[k][2] = W[i][j]; /* weight of edge */
k++;
}
/* display set of edges - before sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %5d", E[i][j]);
printf("\n");
}
printf("\nAfter Sorting According to frequency...\n");
/* sort set of edges in non-decreasing order by weight - bubblesort */
for (i = M - 1; i > 0; i--)
for (j = 0; j < i; j++)
if (E[j][2] > E[j+1][2])
{ a = E[j][0];
b = E[j][1];
c = E[j][2];
E[j][0] = E[j+1][0];
E[j][1] = E[j+1][1];
E[j][2] = E[j+1][2];
E[j+1][0] = a;
E[j+1][1] = b;
E[j+1][2] = c;
}
/* display set of edges - after sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %5d", E[i][j]);
printf("\n");
}
/* create n subsets */
for (i = 0; i < N; i++)
U[i]=i;
/* initialize set of edges in min. span. tree to empty */
for (i = 0; i < N - 1; i++)
for (j = 0; j < 3; j++)
F[i][j] = -1; /* '-1' denotes 'empty' */
/* find minimum spanning tree */
while (num_edges < N - 1)
{ a = E[next_edge][0];
b = E[next_edge][1];
i = find(a);
j = find(b);
if (!equal(i, j))
{ merge (i, j);
F[num_edges][0] = E[next_edge][0];
F[num_edges][1] = E[next_edge][1];
F[num_edges][2] = E[next_edge][2];
num_edges++;
}
next_edge++;
}
/* display edges comprising minimum spanning tree */
printf("\nMinimal Spanning Tree Edges:\n");
printf("F = (");
for (i = 0; i < N - 1; i++)
{ printf("(V%d,V%d)", F[i][0], F[i][1]);
if (i < N - 2)
printf(", ");
weight = weight + F[i][2];
}
printf(")\n");
printf("Minimum cost = %d\n", weight);
return (0);
}
/*************** find() ***************/
int find (int i)
{ int j;
j = i;
while (U[j] != j)
j = U[j];
return (j);
}
/*************** merge() ***************/
void merge (int p, int q)
{ if (p < q)
U[q] = p;
else
U[p] = q;
}
/*************** equal() ***************/
int equal (int p, int q)
{ if (p == q)
return (1);
else
return (0);
}
///////////CLOSE KRUSKAL///////////////////
//////////////////PRIMS/////////////////////
int prims()
{
cout<<"\n\nPrims Algorithm : \n\n";
//read_from_user();
/*near[j] is a vertex in tree such that cost[j][nears[j]] is minimum among all choices for near[j]*/
tr[0][0]=x;
tr[0][1]=l;
int i;
for(int i=0;i<=N-1;i++)
{
if(cost[i][l]<cost[i][x])
nears[i]=l;
else
nears[i]=x;
}
nears[l]=-1;
nears[x]=-1;
///////////////////////////////////////////
/*Find another N-2 edges for minimum spanning tree*/
int j;
for(i=1;i<N-1;i++)
{
j=findmin();
tr[i][0]=j;
tr[i][1]=nears[j];
mincost=mincost+cost[j][nears[j]];
nears[j]=-1;
/* update nears[] */
for(x=0;x<=N-1;x++)
{
if(nears[x]!=-1 && cost[x][nears[x]] > cost[x][j])
nears[x]=j;
}
}
cout<<"Your Given inpus are : \n";
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %5d", E[i][j]);
printf("\n");
}
///////////////////////////////////////////////////
cout<<"\nOUTPUT\n";
cout<<"EDGES SELECTED : \n(";
for(i=0;i<N-1;i++)
{
printf("(V%d,V%d) ", tr[i][0], tr[i][1]);
//cout<<tr[i][0]<<" "<<tr[i][1]<<"\n";
}
cout<<") \nMinimum cost = "<<mincost;
cout<<"\n\n";
}
void read_from_user(void)
{
cout<<"\nEnter number of vertices : ";
cin>>N;
int min=MAXINT;
int i,j;
for(int i=0;i<=N-1;i++)
for(int j=0;j<=N-1 && i!=j;j++)
{
cost[i][j]=MAXINT;
}
for(i=0;i<=N-1;i++)
for(int j=0;j<=N-1;j++)
{
if(i!=j && i<j)
{
cout<<"\nEnter cost between vertex(999 for infinity) "<<i<<" and "<<j<<":";
cin>>cost[i][j]; M++;
W[i][j]=cost[i][j]; //for kruskal
cost[j][i]=cost[i][j]; W[j][i]=W[i][j];
if(min>cost[i][j])
{
min=cost[i][j];
x=i;
l=j;
mincost=min;
}
}
else
{
cost[i][i]=0;
}
}
}
int findmin(void) //for prims
{
int y;
int min=MAXINT;
for(int x=0;x<=N-1;x++)
{
if(nears[x]!=-1 && cost[x][nears[x]]<min)
{
min=cost[x][nears[x]];
y=x;
}
}
return y;
}
int main()
{
int ss,ss2;
tt1:
read_from_user();
tt12:
cout<<"\nEnter solving Algorithm for MST \n1. Kruskal Algorithm\n2. Prim's Algorithm\nPRESS : ";
tt2:
cin>>ss;
if(ss==1) kruskal();
else if(ss==2) prims();
else {cout<<"\npress only 1 or 2 for select\n\nPRESS : ";goto tt2;}
cout<<"\n\nTest with new data or Another algorithm\n\n3. Test with previous data\n4. Input new data\nPRESS : ";
tt3:
cin>>ss2;
if(ss2==3) goto tt12;
else if(ss2==4) goto tt1;
else {cout<<"\npress only 3 or 4 for select\n\nPRESS : ";goto tt3;}
}
