gistfile1.c

#include<stdio.h>
#define INFINITY 9999 /*INFINITY should be larger than the largest cost edge.Instead of blank space in the algo we use infinity here*/
struct coord
{
	int x,y;
};
typedef struct coord coord;
int noPath(int i,int j,int prev,int n,int MST[10][10])
{
	int k,r=1;
	for(k=0;k<n;k++){
		if(MST[i][k]<INFINITY){
			if(k==j)
				r=0;
			else if(k!=i && k!=prev)  
				r=noPath(k,j,i,n,MST);
		}
	}
	return r;
}
coord min(int c[10][10],int MST[10][10],int n)
{
	coord minXY;
	int i,j,minCost=INFINITY;
	minXY.x=-1;
	for(i=0;i<n;i++){
		start:
		for(j=0;j<n;j++)
			if(c[i][j]<minCost){
				if(noPath(i,j,i,n,MST)){
					minXY.x=i;
					minXY.y=j;
					minCost=c[i][j];
				}
				else{
					c[i][j]=INFINITY;
					c[j][i]=INFINITY;
					i=0;
					goto start;
				}
			}
	}
	return minXY;
}
void kruskal(int c[10][10],int n)
{
	int MST[10][10],i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			MST[i][j]=INFINITY;
	coord minXY;
	minXY=min(c,MST,n);
	while(minXY.x!=-1){
		MST[minXY.x][minXY.y]=c[minXY.x][minXY.y];
		MST[minXY.y][minXY.x]=c[minXY.x][minXY.y];
		printf("Added the node %d %d\n",minXY.x+1,minXY.y+1);
		c[minXY.x][minXY.y]=INFINITY;
		c[minXY.y][minXY.x]=INFINITY;
		minXY=min(c,MST,n);
	}
	printf("MST is :\n");
	for(i=0;i<n;i++,printf("\n"))
		for(j=0;j<n;j++)
			printf("%d\t",MST[i][j]);
}	
void main()
{
	int c[10][10],n,i,j;
	printf("Enter the number of nodes :");
	scanf("%d",&n);
	printf("Enter the cost matrix :\n");
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
				scanf("%d",&c[i][j]);
	kruskal(c,n);
}