Home > Source Codes > Software Programs > C++ Programs > Data structure > C++ programs to implement the Kruskal’s algorithm to generate a minimum cost spanning tree

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

Thursday, March 11th, 2010

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

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
 
main()
{
int dup1,dup2;
cout<<"enter no of vertices";
cin >> n;
cout <<"enter no of edges";
cin >>m;
cout <<"EDGE Cost";
for(k=1;k<=m;k++)
{
cin >>i >>j >>c;
cost[i][j]=c;
cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
visit=1;
while(visit<n)
{
v=31999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1 )
{
int count =0;
for(p=1;p<=n;p++)
{
if(visited[p]==i || visited[p]==j)
count++;
}
if(count >= 2)
{
for(p=1;p<=n;p++)
if(cost[i][p]!=31999 && p!=j)
dup1=p;
for(p=1;p<=n;p++)
if(cost[j][p]!=31999 && p!=i)
dup2=p;
 
if(cost[dup1][dup2]==-1)
continue;
}
l=i;
k=j;
v=cost[i][j];
}
cout <<"edge from " <<l <<"-->"<<k;
cost[l][k]=-1;
cost[k][l]=-1;
visit++;
int count=0;
count1=0;
for(i=1;i<=n;i++)
{
if(visited[i]==l)
count++;
if(visited[i]==k)
count1++;
} 
if(count==0)
visited[++vst]=l;
if(count1==0)
visited[++vst]=k;
}
}

OUTPUT

enter no of vertices4
enter no of edges4
EDGE Cost
1 2 1
2 3 2
3 4 3
1 3 3

edge from 1–>2edge from 2–>3edge from 1–>3

Avatar Image

Author Name :
Ranjith

Total : 9 Comments

Simillar Posts

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

  1. MAYURESH says:
    November 8, 2011 at 10:15 am

    Hi!
    Thanks for the program .
    Do you have any idea, so i can implement kruskal’s algorithm with graphics?

  2. Ishan says:
    November 11, 2011 at 11:24 pm

    It doesnt work buddy, for cyclic conditions….

  3. pranoy tez says:
    November 17, 2011 at 6:58 pm

    thnx a lot…

  4. sdkarthi says:
    March 27, 2012 at 7:07 am

    good and thanks

  5. shalini says:
    March 29, 2012 at 3:20 pm

    thank u for your program

  6. Batercus says:
    April 9, 2012 at 7:05 pm

    thanks a lot..

  7. neha says:
    April 16, 2012 at 9:34 am

    plz provide necessary info abt d variables used, lyk wats visit, visited etc

  8. jaydee says:
    April 18, 2012 at 10:28 am

    sorry dude but your program doesn’t work for looping conditions youve gotta eep another counter for loops.

  9. Mz Rokz says:
    May 10, 2012 at 2:36 pm

    You enterd 4 vertices and your output connected only 3 of them….
    Secondly, the output you displayed is making a cycle between vertices 1 2 & 3 which is wrong.
    Your algorithm is bullshit……….

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup