Implementation of Kruskal Algorithm in C/C++ :
   For Disjoint Graphs the Kruskal Algorithm Gives the Minimum Spanning
   Tree for each of the disjoint sets/graphs considered individually.
   NOTE : ALL OUTPUT IS DIRECTED TO A FILE kruskalalgo.txt

-------------------------


# include <stdio.h>
# include <stdlib.h>
void Make_set(int set[]);
int Find_set(int set[],int x);
void Link(int set[],int x1,int x2);
void Display_set(int set[]);
void Make_set(int set[])
 {
 int ctr1;
 for(ctr1=1;ctr1<=set[0];ctr1++)
 set[ctr1]=ctr1;
 };
int Find_set(int set[],int x)
 {
 return set[x];
 }
void Link(int set[],int x1,int x2)
 {
 int ctr1,ctr2,prevVal;
 if(set[x1]==set[x2]) return ;
 if(set[x1]<set[x2])
	{prevVal=set[x2];
	set[x2]=set[x1];
	for(ctr1=1;ctr1<=set[0];ctr1++)
	if(set[ctr1]==prevVal) set[ctr1]=set[x2];
	return ;
	}
 if(set[x2]<set[x1])
	{prevVal=set[x1];
	set[x1]=set[x2];
	for(ctr1=1;ctr1<=set[0];ctr1++)
	if(set[ctr1]==prevVal) set[ctr1]=set[x1];
	return ;
	}
}

struct EdgeOfGraph {
int vertex1,vertex2;
int weight;
};
typedef EdgeOfGraph edge;
void get_Edges(edge *);
void display_Edges(edge *);
void sort_Edges(edge edges[]);
FILE *foutput;
void get_Edges(edge *edges)
{
int ctr1;
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
	{printf("\nEnter the Edge : Starting Vertex , Ending Vertex , Weight of the Edge.\n");
	scanf("%d%d%d",&edges[ctr1].vertex1,&edges[ctr1].vertex2,&edges[ctr1].weight);
	}
}

void display_Edges(edge *edges)
{
int ctr1;
printf("\n");
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
fprintf(foutput,"[ Vertex1: %d , Vertex2: %d , Weight: %d ]\n",edges[ctr1].vertex1,edges[ctr1].vertex2,edges[ctr1].weight);
fprintf(foutput,"\n");
}

void sort_Edges(edge edges[])
{
int ctr1,ctr2,ctr3;
edge temp;
for(ctr1=2;ctr1<=edges[0].weight;ctr1++)
	{
	temp=edges[ctr1];
	ctr2=ctr1;
	while(ctr2>1 && temp.weight<edges[ctr2-1].weight)
	{edges[ctr2]=edges[ctr2-1];
	ctr2--;
	};
	if(ctr2!=ctr1)
	edges[ctr2]=temp;
	}
}

void implementKruskal(edge*,edge*,int set[]);
void implementKruskal(edge edges[],edge edgesOfTree[],int set[])
{int ctr1,ctr2=1;
 for(ctr1=1;ctr1<=edges[0].weight;ctr1++)
 {if(set[edges[ctr1].vertex1]!=set[edges[ctr1].vertex2])
   {
   Link(set,edges[ctr1].vertex1,edges[ctr1].vertex2);
   edgesOfTree[ctr2++]=edges[ctr1];
   };
  }
  edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=ctr2-1;
}

int main()
{edge *edges,*edgesOfTree;
int v1,v2,nEdges,nVertices,*set;
foutput=fopen("kruskalalgo.txt","a");
printf("\nALL OUTPUT WILL BE DIRECTED TO THE FILE kruskalalgo.txt .\n");
printf("\nEnter the Number of Vertices , Edges . (Vertices are from 1.....n) .");
scanf("%d%d",&nVertices,&nEdges);
fprintf(foutput,"\n No of Edges=%d ,No of Vertices=%d.\n",nEdges,nVertices);
set=(int *)malloc(sizeof(int) * (nVertices+1));
edges=(edge *)malloc(sizeof(edge) * (nEdges+1));
edgesOfTree=(edge *)malloc(sizeof(edge) * (nEdges+1));
edges[0].vertex1=edges[0].vertex2=edges[0].weight=nEdges;
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=nEdges;
get_Edges(edges);
sort_Edges(edges);
fprintf(foutput,"The Edges Entered ( in Ascending Order of Weights ) :\n");
display_Edges(edges);
set[0]=nVertices;
Make_set(set);
implementKruskal(edges,edgesOfTree,set);
fprintf(foutput,"\nEdges Included in the Minimum Spanning Tree are:\n");
display_Edges(edgesOfTree);
fclose(foutput);
return 0;
}


OUTPUT FILE : 

No of Edges=12 ,No of Vertices=8.
The Edges Entered ( in Ascending Order of Weights ) :
[ Vertex1: 2,Vertex2: 3,Weight: 1 ]
[ Vertex1: 5,Vertex2: 6,Weight: 1 ]
[ Vertex1: 7,Vertex2: 8,Weight: 1 ]
[ Vertex1: 3,Vertex2: 4,Weight: 3 ]
[ Vertex1: 2,Vertex2: 4,Weight: 3 ]
[ Vertex1: 6,Vertex2: 8,Weight: 3 ]
[ Vertex1: 1,Vertex2: 3,Weight: 4 ]
[ Vertex1: 8,Vertex2: 5,Weight: 4 ]
[ Vertex1: 5,Vertex2: 7,Weight: 4 ]
[ Vertex1: 1,Vertex2: 2,Weight: 5 ]
[ Vertex1: 4,Vertex2: 1,Weight: 6 ]
[ Vertex1: 6,Vertex2: 7,Weight: 7 ]


Edges Included in the Minimum Spanning Tree are:
[ Vertex1: 2,Vertex2: 3,Weight: 1 ]
[ Vertex1: 5,Vertex2: 6,Weight: 1 ]
[ Vertex1: 7,Vertex2: 8,Weight: 1 ]
[ Vertex1: 3,Vertex2: 4,Weight: 3 ]
[ Vertex1: 6,Vertex2: 8,Weight: 3 ]
[ Vertex1: 1,Vertex2: 3,Weight: 4 ]


 No of Edges=11 ,No of Vertices=9.
The Edges Entered ( in Ascending Order of Weights ) :
[ Vertex1: 1 , Vertex2: 2 , Weight: 1 ]
[ Vertex1: 5 , Vertex2: 1 , Weight: 1 ]
[ Vertex1: 6 , Vertex2: 7 , Weight: 1 ]
[ Vertex1: 2 , Vertex2: 3 , Weight: 2 ]
[ Vertex1: 4 , Vertex2: 5 , Weight: 2 ]
[ Vertex1: 8 , Vertex2: 9 , Weight: 2 ]
[ Vertex1: 2 , Vertex2: 5 , Weight: 3 ]
[ Vertex1: 7 , Vertex2: 8 , Weight: 3 ]
[ Vertex1: 6 , Vertex2: 8 , Weight: 4 ]
[ Vertex1: 9 , Vertex2: 6 , Weight: 5 ]
[ Vertex1: 3 , Vertex2: 4 , Weight: 6 ]


Edges Included in the Minimum Spanning Tree are:
[ Vertex1: 1 , Vertex2: 2 , Weight: 1 ]
[ Vertex1: 5 , Vertex2: 1 , Weight: 1 ]
[ Vertex1: 6 , Vertex2: 7 , Weight: 1 ]
[ Vertex1: 2 , Vertex2: 3 , Weight: 2 ]
[ Vertex1: 4 , Vertex2: 5 , Weight: 2 ]
[ Vertex1: 8 , Vertex2: 9 , Weight: 2 ]
[ Vertex1: 7 , Vertex2: 8 , Weight: 3 ]


 No of Edges=10 ,No of Vertices=11.
The Edges Entered ( in Ascending Order of Weights ) :
[ Vertex1: 1 , Vertex2: 2 , Weight: 1 ]
[ Vertex1: 2 , Vertex2: 3 , Weight: 1 ]
[ Vertex1: 4 , Vertex2: 5 , Weight: 2 ]
[ Vertex1: 8 , Vertex2: 9 , Weight: 2 ]
[ Vertex1: 9 , Vertex2: 11 , Weight: 2 ]
[ Vertex1: 9 , Vertex2: 10 , Weight: 3 ]
[ Vertex1: 5 , Vertex2: 7 , Weight: 4 ]
[ Vertex1: 8 , Vertex2: 10 , Weight: 4 ]
[ Vertex1: 1 , Vertex2: 3 , Weight: 5 ]
[ Vertex1: 4 , Vertex2: 6 , Weight: 5 ]


Edges Included in the Minimum Spanning Tree are:
[ Vertex1: 1 , Vertex2: 2 , Weight: 1 ]
[ Vertex1: 2 , Vertex2: 3 , Weight: 1 ]
[ Vertex1: 4 , Vertex2: 5 , Weight: 2 ]
[ Vertex1: 8 , Vertex2: 9 , Weight: 2 ]
[ Vertex1: 9 , Vertex2: 11 , Weight: 2 ]
[ Vertex1: 9 , Vertex2: 10 , Weight: 3 ]
[ Vertex1: 5 , Vertex2: 7 , Weight: 4 ]
[ Vertex1: 4 , Vertex2: 6 , Weight: 5 ]