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?

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

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

    Reply
  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.
    Your algorithm is bullshit……….

    Reply
    • ShuFeng Li

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

      Reply
  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;
    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;
    }

    Reply
  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

    Reply

Leave a Reply