#include<iostream.h>
#include<stdio.h>
int parent[10]; //initial value 0 due to global initialization
class kruskal
{
int a,b,u,v,i,j,n,noofedges;
int visited[10],min,mincost,cost[10][10];
public:
kruskal()
{
noofedges=1;
mincost=0;
}
void read();
void kruskals(int cost[][10],int n);
};
void kruskal::read()
{
cout<<"Enter the no. of vertices";
cin>>n;
cout<<"Enter the adjacency matrices";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999;
}
kruskals(cost,n);
}
void kruskal::kruskals(int cost[][10],int n)
{
cout<<"The minimum cost edges are \n";
while(noofedges<n)
{
min=999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
noofedges++;
cout<<"\n Edge ( "<<a<<"->"<<b<<")"<<min;
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
cout<<"\n \n Minimum cost \t"<<mincost<<" ";
}
main()
#include<stdio.h>
int parent[10]; //initial value 0 due to global initialization
class kruskal
{
int a,b,u,v,i,j,n,noofedges;
int visited[10],min,mincost,cost[10][10];
public:
kruskal()
{
noofedges=1;
mincost=0;
}
void read();
void kruskals(int cost[][10],int n);
};
void kruskal::read()
{
cout<<"Enter the no. of vertices";
cin>>n;
cout<<"Enter the adjacency matrices";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999;
}
kruskals(cost,n);
}
void kruskal::kruskals(int cost[][10],int n)
{
cout<<"The minimum cost edges are \n";
while(noofedges<n)
{
min=999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
while(parent[u])
u=parent[u];
while(parent[v])
v=parent[v];
if(u!=v)
{
noofedges++;
cout<<"\n Edge ( "<<a<<"->"<<b<<")"<<min;
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
cout<<"\n \n Minimum cost \t"<<mincost<<" ";
}
main()
No comments:
Post a Comment