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

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

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

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

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

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

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

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

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

  7. Pingback: filmy videobb

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s