# 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:
Graph:Adjacency Matrix

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

int tree;

int sets;
int top;
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};

void kruskal::read_graph()
{
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]=i;
graph_edge[noe]=j;
graph_edge[noe]=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]
<<” , “<<graph_edge[i]
<<” > ::”<<graph_edge[i]<<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]>graph_edge[j+1])
{
int t=graph_edge[j];
graph_edge[j]=graph_edge[j+1];
graph_edge[j+1]=t;

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

t=graph_edge[j];
graph_edge[j]=graph_edge[j+1];
graph_edge[j+1]=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]
<<” , “<<graph_edge[i]
<<” > ::”<<graph_edge[i]<<endl;
}

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

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

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

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

tree[graph_edge[i]][graph_edge[i]]=graph_edge[i];
tree[graph_edge[i]][graph_edge[i]]=graph_edge[i];

// 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]<<” , ”
<<graph_edge[i]<<” > “<<“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.read_graph();
obj.sort_edges();
obj.algorithm();
return 0;
}

Advertisements

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

1. Lok P Acharya says:

Hello

I find this useful.

Lok

2. Roopa says:

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.

3. ladi says:

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.

5. vinod & vara prasad says:

may i know what is wrong with the code

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.

6. papyrus says:

Thank you for this useful notes & programs.

7. 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.

8. 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…

9. 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…

10. varun kumar c k says:

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

11. kel says:

thnx for the code… nicely done

12. vimal kumar says:

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

13. babbar says:

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

14. 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??

15. Heartburn Home Remedy says:

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.

16. 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?

17. owes says:

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

18. owes says:

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

19. aniket says:

exactly what i needed…..
thanks….

20. uche says:

thank God for ur code, it was very useful

21. 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

22. mr.park says:

hi i love heowook

23. mr.won says:

my name is won

i like girl in whadongjang

24. mr.park says:

thanks!!!!!!

this is what i wanted!

25. raghav says:

thank you

26. Satya says:

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

27. Aadi says:

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

28. akshay says:

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

29. JAYPEE says:

This site provide good program

30. anusha says:

this weeb site is very useful

31. Ramya says:

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

32. rajeshwari says:

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

33. Pingback: filmy videobb
34. vs says:

post with o/p