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

/* 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

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

1. MAYURESH

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

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

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

4. Mz Rokz

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.

• ShuFeng Li

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

5. Surbhi bhattar

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;

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)
{
}
else
{
if(i==j)
else
}
}
}
}

int k=0,count=0;

void filter()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;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;
}

6. plz write the full names of variables declared it is very very very… difficult to understand .while using function plz write comment for that