Kruskal’s algorithm

/*
* Status: Tested OK
* Title: Kruskal's Algorithm
* Name: Akshay Thakare
*/

#include <stdio.h>
#include <stdlib.h>

#define EMPTY 9999

int *start, *end, *weight;
int *u;
int n,v,cost;

void sort();
int search();
void unions(int m);
void krusk();

int main()
{
	int i,j;
	
	printf("Enter the number of vertices of the graph = ");
		scanf("%d",&v);
	
	printf("\nEnter the number of edges in the graph = ");
		scanf("%d",&n);

	start = malloc(n*sizeof(int));
	end = malloc(n*sizeof(int));
	weight = malloc(n*sizeof(int));
	
	printf("NOTE: VERTICES ARE LABELLED FROM 0 TO N not 1 to N");
	for(i=0;i<n;i++)
	{
		printf("\nEnter a start and end vertex of edge %d below along with its weight\n",i+1);
		scanf("%d",&start[i]);
		scanf("%d",&end[i]);
		scanf("%d",&weight[i]);
	}

	krusk();	
	return 0;
}

void sort()
{
	int i,j,temp;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(weight[i]<weight[j])
			{
				temp = weight[j];
				weight[j] = weight[i];
				weight[i] = temp;
				
				temp = start[j];
				start[j] = start[i];
				start[i] = temp;
				
				temp = end[j];
				end[j] = end[i];
				end[i] = temp;
			}
		}
	}
}

int search(int x)
{
	int i;
	for(i=0;i<v;i++)
	{
		if(u[i]==x)
			return 0;
	}
	return 1;
}

void unions(int m)
{
	int i;
	for(i=0;i<v;i++)
		if(u[i]==EMPTY)
		{
			u[i]=m;
			return;
		}
}

void krusk()
{
	int i,v_copy;
	v_copy = v;
	int flag;
	cost=0;
	
	sort();
	
	u = malloc(v*sizeof(int));		//Make set array
	for(i=0;i<v;i++)
		u[i]=EMPTY;
		
	i=0;
	while(v_copy!=0)
	{	
		flag=0;
		if(search(start[i]))
		{
			flag=1;
			unions(start[i]);
			printf("%d ",start[i]+1);
		}
		if(search(end[i]))
		{
			flag=1;
			unions(end[i]);
			printf("%d ",end[i]+1);
		}
		
		if(flag==1)
			cost+=weight[i];
		
		v_copy--;
		i++;
	}
	printf("\nCost = %d",cost);
}

Advertisements

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