kruskal's algorithm

 

#include<iostream>

using namespace std;

int adj[10][10],parent[10];

int a,b,u,v,min_cost=0;

int find(int u)

{

while(parent[u])

u=parent[u];

return u;

 

}

int uni(int u,int v)

{if(u!=v)

{parent[v]=u;

return 1;

}

else return 0;

 

}

int main()

{

 

int n,e;

cout<<"\n enter vertex and edge";

cin>>n>>e;

int i,j;

while(e--)

{

cout<<"\n enter vertices between which you want an edge";

cin>>i>>j;

cout<<"\n enter the weight";

cin>>adj[i-1][j-1];

adj[j-1][i-1]=adj[i-1][j-1];

}

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(adj[i][j]==0)

{adj[i][j]=9999;

adj[j][i]=9999;

}

}

}

int min;int edge=0;

while(edge<n)

{min=9999;

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

  if(adj[i][j]<min)

{min=adj[i][j];

a=u=i;

b=v=j;

}}}

u=find(u);

v=find(v);

if(uni(u,v))

{

cout<<"edge between"<<a+1<<"\t"<<b+1<<"\twith weight "<<min<<"\n";

edge++;

min_cost+=min;

}

adj[a][b]=adj[b][a]=9999;

}

cout<<"\n minimum spanning cost is"<<min_cost;

return 0;

}