C code for Kruskal Algorithm

Kruskal algorithm is one of the two commonly used algorithms for finding a Minimum Spanning Tree. Here the C code for implementing this algorithm has been presented. The code operates on the Input File which can be downloaded and must be in the same directory in which the program is to be executed. This code can be made to operate on any graph which is represented in adjacency matrix of size n*n and the 1st row 1st column contains the value of n, as represented in the file input file, dist.txt

Programming Geeks : C code for Kruskal algorithm

#include “stdio.h”

#define MAX 50
#define INFINITY 4000

void inputgraph(int);
void makeset(int);
void findmin(int);
int findset(int);
void unionset(int,int);

int wt[MAX][MAX];
int edge[MAX][MAX];
int edge1,edge2;
int c = INFINITY;
int mstree[ 2*MAX];
int n;
int set[MAX];
int flag;
int tedge = 0;

main()
{
int i,j;
int k=0;
FILE *f = fopen(“dist.txt”, “r”);
fscanf(f, “%d”, &n);
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
{
fscanf(f, “%d”, &wt[i][j]);
if(wt[i][j] == 0)
{
edge[i][j] = 0;
edge[j][i] = 0;
}
if(wt[i][j] != 0)
{
edge[i][j] = 1;
edge[j][i] = 1;
tedge = tedge + 2;
}
}
fclose(f);

makeset(n);

for(i = 1;i<=tedge;i++)
{

findmin(n);
if(findset(edge1) != findset(edge2))
{
mstree[k++] = edge1;
mstree[k++] = edge2;
edge[edge1][edge2] = 0;
unionset(edge1,edge2);
}
}
k=0;
flag = 1;
for(i = 0;i

{
printf(“Edge no. %d of minimum spanning tree hv vertices %d and %d \n”,flag,mstree[k],mstree[k+1]);
flag++;
k = k+2;
}

}

void makeset(int n)
{
int i;
for (i=1;i<=n;i++)
{
set[i] = i;

}
}

void findmin(int n)
{
int i,j;
for (i=0;i

{
for(j=i;j<=n;j++)
{
if(edge[i][j] == 1)
{
if(wt[i][j] <= c)
{
c = wt[i][j];
edge1 = i;
edge2 = j;

}
}
}
}
edge[edge1][edge2]= 0;
c = INFINITY;
}

int findset( int a)
{
return set[a];
}

void unionset(int a,int b)
{
int z;
int temp;
temp = set[b];
set[b] = set[a];
for(z = 0;z

{
if(set[z] == temp)
{
set[z] = set[a];
}
}
}


Related Posts

Share

Filed Under: CCodes

About the Author: Software Engineer - Advanced Search & Recommendation at Rovi

RSSComments (2)

Leave a Reply | Trackback URL

  1. Hi, Very interesting article. I am quite impressed and just wanted to let you know that you did a fine job on this article. However, I do have some unanswered questions that I would like to ask you. I will contact you via email so that you can clear some of these things up for me. Again, very well written article. Keep up the good work.

  2. Salma says:

    Hello, thanks alot for this post! quiet intresting, though i do have some questions about functions you’ve used in your program, so i am wondering if i can contact via email?

Leave a Reply

*

AWSOM Powered