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

-> 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[100][4];

int tree[10][10];

int sets[100][10];

int top[100];

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][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.read_graph();

obj.sort_edges();

obj.algorithm();

return 0;

}

Hello

I find this useful.

Lok

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

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

may i know what is wrong with the code

what is wrong with this code?

if u know the correct code then send me the correct code in my id

ajitpandey@yahoo.in

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.

Thank you for this useful notes & programs.

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.

It was giving errors at first..

but i changed the variable name where it was giving errors..

its working fine now..

thanks a lot…

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…

Thanku you very much

This will be very useful for my innovative work

thnx for the code… nicely done

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

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

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

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

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.

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?

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

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

exactly what i needed…..

thanks….

thank God for ur code, it was very useful

hi my name is sim

i’m from korea

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

hi sim my friend

hi i love heowook

my name is won

i like girl in whadongjang

thanks!!!!!!

this is what i wanted!

thank you

Thanx. Its good work.

Simple and easy to understand..

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

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

This site provide good program

this weeb site is very useful

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

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

post with o/p