# Kruskal’s Algorithm for Minimum Spanning Tree

/************************************************************

-> This Program is to implement Kruskal algorithm.

-> This program is to find minimum spanning tree
for undirected weighted graphs

-> Data Structers used:

-> This program works in microsoft vc++ 6.0 environment.

**************************************************************/

#include<iostream.h>
class kruskal
{
private:
int n; //no of nodes
int noe; //no edges in the graph
int graph_edge[100][4];

int tree[10][10];

int sets[100][10];
int top[100];
public:
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};

{
cout<<“*************************************************\n”
<<“This program implements the kruskal algorithm\n”
<<“*************************************************\n”;
cout<<“Enter the no. of nodes in the undirected weighted graph ::”;
cin>>n;

noe=0;

cout<<“Enter the weights for the following edges ::\n”;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<” < “<<i<<” , “<<j<<” > ::”;
int w;
cin>>w;
if(w!=0)
{
noe++;

graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}

// print the graph edges

cout<<“\n\nThe edges in the given graph are::\n”;
for(i=1;i<=noe;i++)
cout<<” < “<<graph_edge[i][1]
<<” , “<<graph_edge[i][2]
<<” > ::”<<graph_edge[i][3]<<endl;

}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;

t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;

t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}

// print the graph edges

cout<<“\n\nAfter sorting the edges in the given graph are::\n”;
for(i=1;i<=noe;i++)
cout<<” < “<<graph_edge[i][1]
<<” , “<<graph_edge[i][2]
<<” > ::”<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}

cout<<“\nThe algorithm starts ::\n\n”;

for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

if(p1!=p2)
{
cout<<“The edge included in the tree is ::”
<<” < “<<graph_edge[i][1]<<” , ”
<<graph_edge[i][2]<<” > “<<endl<<endl;

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}

top[p2]=0;
}
else
{
cout<<“Inclusion of the edge ”
<<” < “<<graph_edge[i][1]<<” , ”
<<graph_edge[i][2]<<” > “<<“forms a cycle so it is removed\n\n”;
}
}
}

int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}

int main()
{
kruskal obj;
obj.sort_edges();
obj.algorithm();
return 0;
}

## 38 thoughts on “Kruskal’s Algorithm for Minimum Spanning Tree”

1. Lok P Acharya says:

Hello

I find this useful.

Lok

2. Hello

I find it very useful ,I am doing my MCA in IGNOU,the subjects are very hard .Always I will search in Net to take the useful notes.

Thank you for this useful notes & programs.

this site is just the bomb as a reference to my project

4. Silent says:

This code is so ugly, not like the work of a professional programmer.

1. Ajit says:

what is wrong with this code?
if u know the correct code then send me the correct code in my id
ajitpandey@yahoo.in

2. elphenomeno says:

if you don’t know what’s wrong with the code here then no one can really help you out.
programming is an art, and this isn’t the work of an artist more of a laborer.

5. papyrus says:

Thank you for this useful notes & programs.

6. Tamal says:

This coding can’t run by any compiler it is very tough to correct this program by any compiler. So do it in a easy way that anybody can easily understand your code and implement in a simplest way. Anyway Thank you for providing this code.
Tamal
JU
Dhaka.

7. Sumit Bagga says:

It was giving errors at first..
but i changed the variable name where it was giving errors..
its working fine now..
thanks a lot…

8. nilesh says:

i am mca student …may i get more Data structure Subject notes or links for that by you? i/have a great intrest for the algorithm design techniques so in case for that may u help me pls…

9. varun kumar c k says:

Thanku you very much
This will be very useful for my innovative work

10. kel says:

thnx for the code… nicely done

11. this is very interesting website which is very usefull to the student as me

12. babbar says:

hi,i like this site very much since it is informative

13. praveen says:

hi , i am a lecturer in engineering college i need c code of this problem in simple manner so pls send me this on my email thanks a lot

1. elphenomeno says:

you are a lecturer in a college and you can’t write code for this,
what’s worse is that you can’t translate this shit into c,
for what do you get a salary son??

14. I read your posts for a long time and must tell that your posts always prove to be of a high value and quality for readers.

15. Blasco says:

Hi,
this code works only if the number of nodes is less or equal than 14 ?!
Could you comment the line of code in which you make the union please?

16. owes says:

thnks , indeed very good algorithm.. for kruskal’s technique

17. owes says:

the program works very efficiently in turbo c++ compiler and vc++ too

18. aniket says:

exactly what i needed…..
thanks….

19. uche says:

thank God for ur code, it was very useful

20. mr.sim says:

hi my name is sim

i’m from korea

i’m a student and majoring in computer software in kw university

1. mr.park says:

hi sim my friend

21. mr.park says:

hi i love heowook

22. mr.won says:

my name is won

23. mr.park says:

thanks!!!!!!

this is what i wanted!

24. raghav says:

thank you

25. Satya says:

Thanx. Its good work.
Simple and easy to understand..

it is a useful code anyway please use comments for better understanding for initial programmers.

27. akshay says:

nice prog….. jst replace the symbol by (“) symbol… thnx….

28. JAYPEE says:

This site provide good program

29. anusha says:

this weeb site is very useful

30. Ramya says:

Hi..i want this program in c coding to my mail id for better understanding to my mail id..

31. rajeshwari says:

ya code is good but if you put output also then it looks very good

32. Pingback: filmy videobb