C++ programs to implement the Kruskal’s algorithm to generate a minimum cost spanning tree

5 thoughts on “C++ programs to implement the Kruskal’s algorithm to generate a minimum cost spanning tree”

1. tree contains a cycle….. amazing….!!!!!!!

2. well i think the below code is right and it does check for cyclic condition….

   // kruskal minimum spanning tree
   #include
   #include

   //structure for graph

   struct str{
   int edge,n1,n2;
   }s0[20],s1[20];

   //structure for checking nodes

   struct st{
   int val,flag;
   }s2[20];

   void input();
   void filter();
   void sort();
   void min();
   void update(int,int,int);

   int n,e,cnt=0,Tcost=0;
   int link[10][10];

   void main()
   {
   clrscr();
   input();
   cout<<"this is filtered output\n";
   filter();
   cout<<"this is sorted output\n";
   sort();
   min();
   cout<<"\nTcost is "<<Tcost;
   getch();
   }

   void input()
   {
   cout<>n>>e;
   cout<<"enter input for upper triangle matrix\n";
   for(int i=0;i<n;i++)
   {
   for(int j=0;ji)
   {
   cout<<"enter link of node "<<i<<" to node "<<j<>link[i][j];
   }
   else
   {
   if(i==j)
   link[i][j]=0;
   else
   link[i][j]=link[j][i];
   }
   }
   }
   }

   int k=0,count=0;

   void filter()
   {
   for(int i=0;i<n;i++)
   {
   for(int j=0;j<n;j++)
   {
   if(link[i][j]!=0)
   {
   s0[k].edge=link[i][j];
   s0[k].n1=i;
   s0[k].n2=j;
   k++;
   count++;
   }
   }
   }
   i=0;
   int j=0;
   int flag=1;
   for(int l=0;l<count;l++)
   {
   if(i==0)
   {
   s1[j].edge=s0[i].edge;
   s1[j].n1=s0[i].n1;
   s1[j].n2=s0[i].n2;
   i++;
   j++;
   }
   else
   {
   k=0;
   while(k<j)
   {
   if(s1[k].edge==s0[i].edge && s1[k].n1==s0[i].n2 && s1[k].n2==s0[i].n1)
   {
   flag=0;
   break;
   }
   else
   k++;
   }
   if(flag)
   {
   s1[j].edge=s0[i].edge;
   s1[j].n1=s0[i].n1;
   s1[j].n2=s0[i].n2;
   i++;
   j++;
   cnt++;
   }
   else
   {
   i++;
   flag=1;
   }
   }
   }
   for(i=0;i<=cnt;i++)
   cout<<s1[i].edge<<"\t"<<s1[i].n1<<"\t"<<s1[i].n2<<"\n"<<endl;
   }

   void sort()
   {
   for(int i=0;i<=cnt-1;i++)
   {
   for(int j=0;js1[j+1].edge)
   {
   int t=s1[j].edge;
   s1[j].edge=s1[j+1].edge;
   s1[j+1].edge=t;

   int t1=s1[j].n1;
   s1[j].n1=s1[j+1].n1;
   s1[j+1].n1=t1;

   int t2=s1[j].n2;
   s1[j].n2=s1[j+1].n2;
   s1[j+1].n2=t2;
   }
   }
   }
   for(i=0;i<=cnt;i++)
   cout<<s1[i].edge<<"\t"<<s1[i].n1<<"\t"<<s1[i].n2<<endl;

   }

   void min()
   {

   //initialize s2 structure

   for(int i=0;i<n;i++)
   {
   s2[i].val=i;
   s2[i].flag=i+1;
   }

   int u,v,y,z;
   int cur=n;

   for(i=0;i<e;i++)
   {
   y=s1[i].n1;
   z=s1[i].n2;
   //cout<<"y & z "<<y<<z;
   u=s2[y].flag;
   v=s2[z].flag;
   if(u!=v){
   Tcost+=s1[i].edge;
   cout<<"\nedge "<<y<“<<z;
   }
   cur=cur+1;
   update(y,z,cur);
   }
   }

   void update(int y,int z,int cur)
   {
   for(int i=0;i<n;i++)
   {
   if(i!=y)
   {
   if(s2[y].flag==s2[i].flag)
   s2[i].flag=cur;
   }

   if(i!=z)
   {
   if(s2[z].flag==s2[i].flag)
   s2[i].flag=cur;
   }
   }
   s2[y].flag=cur;
   s2[z].flag=cur;
   }

3. I think different than you sir. Please have look at following code. Its small piece of code but full implemtentation of Klusker’s Algorithm in C++.

   http://in.docsity.com/en-docs/Kruskals_Algorithm_-_C_plus_plus_Code

4. Its a error free and easily run in TC4.5<<<cin

5. The can’t work nomally.The result is wrong.The right order is 1–>2—>3—>4.