I need to know how to implement Kruskal\'s algorithm using anadjacency matrix, a
ID: 3615736 • Letter: I
Question
I need to know how to implement Kruskal's algorithm using anadjacency matrix, and union/find partition class. Ihave the union/find partition class done, and I have the graph in a2-D array, I don't understand Kruskal's algorithm from this point,could anyone help me. though, this is what I am supposed todo: If you need to see any code just send me a message. partition p Sort edges of Graph G ST = ' ' length = 0 while(|ST| <n-1 { (x.y) = next edge on list if(p,uf_find(x) !=p.uf_find(y)) { (x,y) joins ST length += weight(x,y) p.uf_union(x,y) } } ST is a minimum spanning tree length is the total weight I need to know how to implement Kruskal's algorithm using anadjacency matrix, and union/find partition class. Ihave the union/find partition class done, and I have the graph in a2-D array, I don't understand Kruskal's algorithm from this point,could anyone help me. though, this is what I am supposed todo: If you need to see any code just send me a message. partition p Sort edges of Graph G ST = ' ' length = 0 while(|ST| <n-1 { (x.y) = next edge on list if(p,uf_find(x) !=p.uf_find(y)) { (x,y) joins ST length += weight(x,y) p.uf_union(x,y) } } ST is a minimum spanning tree length is the total weightExplanation / Answer
Dear,
#include<iostream.h>
#include<conio.h>
class Sets
{
public:
int p[10],n;
Sets(int n1)
{
n=n1;
for(int i=1;i<=n;i++)
p[i]=-1;
}
void setunion(int i,int j)
{
p[i]=j;
}
int setfind(int i)
{
while(p[i]>=0)
i=p[i];
return i;
}
};
void main() //MainFunction
{
int adj[20][20],cost[20][20],t[10][10];
int ru,rv,n,m,d,k=0,c1,c2,mincost=0;
clrscr();
cout<<"Please enter the no.ofvertices"<<endl;
cin>>n;
Sets s(n);
cout<<"Please enter the adjacencymatrix"<<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>adj[i][j];
for(i=1;i<=n-1;i++)
for(d=1;d<=n-i;d++)
{
j=i+d;
if(adj[i][j]!=0)
{
k++;
cost[k][1]=adj[i][j];
cost[k][2]=i;
cost[k][3]=j;
}
}
for(i=1;i<=k-1;i++)
{
for(j=1;j<=k-i;j++)
if(cost[j][1]>cost[j+1][1])
{
for(int p=1;p<=3;p++)
{
int temp=cost[j][p];
cost[j][p]=cost[j+1][p];
cost[j+1][p]=temp;
}
}
}
int count=1;j=1;
while(i<=n-1 || j<=k)
{
ru=s.setfind(cost[j][2]);
rv=s.setfind(cost[j][3]);
if(ru!=rv)
{
t[count][1]=cost[j][2];
t[count][2]=cost[j][3];
mincost+=cost[j][1];
s.setunion(ru,rv);
count++;
}
j++;
}
cout<<" The edges includes in the minimum costspanning tre are"<<endl;
for(int l=1;l<=count-1;l++)
cout<<"("<<t[l][1]<<","<<t[l][2]<<")"<<" ";
cout<<" The cost of the spanning tree is "<<mincost;
getch();
}//END OF PROGRAM
I hope this will helps you!!!!!!!!!!!