Program to implement Kruskal’s algorithm

// KRUSKALS 
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define m 99
template<class t>
class KRUS
{	int flag[5],spantree[2][5],graph[][5];
	public:
		void KRU()
		{	int mincost=0;
			int edges=0;
			int i,j;
			for(i=0;i<5;i++)
			{for(j=0;j<5;j++)
				{
					cin>>graph[i][j];
				}
				cout<<"\n";
			}for(i=0;i<5;i++)
			flag[i]=0;
			printarray(flag);
			while(edges<4)
			{	findminedge(&i,&j);
				if(!(flag[i]&&flag[j]))
				{	spantree[0][edges]=i;
					spantree[1][edges]=j;
					if(!flag[i])
					flag[i]=1;
					if(!flag[j])
					flag[j]=1;
					cout<<mincost<<"\n";
					mincost+=graph[j][i];
					edges++;
					printarray(flag);
					cout<<"\n the edge is accepted"<<i<<"j<<"\n";
					getch();
				}else  
	cout<<"\n the edge is rejected"<<i<<"  "<<j<<"\n";  }
			printmintree();	cout<<"\n mincost="<<mincost;
		}void printarray(int a[5])
		{for(int i=0;i<5;i++)
			cout<<"  "<<a[i];
			cout<<"\n";
		}void printmintree()
		{for(int i=0;i<4;i++)
			cout<<spantree[0][i]<<"  "<<spantree[1][i]<<"\n";
		}
		void findminedge(int *a,int *b)
		{int i,j,min=99;
			for(i=0;i<5;i++)
			{for(j=0;j<5;j++)
				{if(graph[i][j]<min)
					{min=graph[i][j];
						*a=i;
						*b=j;}}}graph[*a][*b]=99;}void main()
{	clrscr();	KRUS<int>v;	v.KRU();getch();
}
Chitra
Chitra

Leave a Reply

Your email address will not be published. Required fields are marked *

Get the latest updates on your inbox

Be the first to receive the latest updates from Codesdoc by signing up to our email subscription.

    StudentProjects.in