/*
*******************************************************************************
This Program is for obtaining the Minimum Spanning Tree by using Kruskal's
minimum spanning tree algorithm . The graph is an weighted undirected graph.
The graph is taken in Adjacency Matrix form.
*******************************************************************************
*/
/List Of Header Files & Constant/
#include<stdio.h>
#include<conio.h>
#define size 20
/* structure for Vertex of Graph*/
struct edge
{
int i,j,wt;
}e[size];
/*
collect_edges Function-for getting the weighted graph
Called By:main()
Calls:none
Input:the weighted graph g,number of edges n.
*/
int collect_edges(int g[size][size],int n,struct edge e[])
{
int i,j,k=0;
printf("\n The Edges Are ==> \n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(g[i][j])
{
e[k].i=i;
e[k].j=j;
e[k].wt=g[i][j];
printf("%2d - %2d = %4d\n",e[k].i,e[k].j,e[k].wt);
k++;
}
return(k);
}
/*
sort_edges Function-sorting the edges according to their weights in the graph
Called By:main()
Calls:none
Input:All the edges in g,number of edges m.
*/
void sort_edges(struct edge e[],int m)
{
int i,j,temp,temp1,temp2;
for(i=0;i<m;i++)
for(j=i+1;j<=m-1;j++)
if(e[i].wt>e[j].wt)
{
temp1=e[j].i;
e[j].i=e[i].j;
e[i].j=temp1;
temp2=e[j].j;
e[j].j=e[i].i;
e[i].i=temp2;
temp=e[j].wt;
e[j].wt=e[i].wt;
e[i].wt=temp;
}
/*
dispaly_spanning Function-dispalys the edges with their weights forming the
spanning tree
Called By:form_spanning()
Calls:none
Input:graph g,number of edges n.
*/
void display_spanning(int g[size][size],int n)
{
int i,j;
printf("\n The Spanning Tree Is ==> ");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(g[i][j])
printf("%2d - %2d = %4d\n",i,j,g[i][j]);
}
/*
form_spanning Function
Called By:form_spanning()
Calls:dispaly_spanning()
Input:edges e,number of edges n.
*/
void form_spanning(struct edge e[],int m,int s[size][size],int n)
{
int i,j,k,c1,c2,l;
int comp=0,visited[size];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s[i][j]=0;
for(i=0;i<n;i++)
visited[i]=0;
for(k=0;k<m;k++)
{
if(visited[e[k].i]==0)
if(visited[e[k].j]==0)
{
comp++;
/both vertices are notvisited/visited[e[k].i]=comp;
/*so form a new component */visited[e[k].j]=comp;
s[e[k].i][e[k].j]=e[k].wt;
s[e[k].j][e[k].i]=e[k].wt;
}
else
{
/connectthe ith vertex/ visited[e[k].i]=visited[e[k].j];
/to the component to/ s[e[k].i][e[k].j]=e[k].wt;
/which j belongs/ s[e[k].j][e[k].i]=e[k].wt;
}
else
if(visited[e[k].j]==0)
{
/connect the jth vertex/visited[e[k].j]=visited[e[k].i];
/*to the component to */s[e[k].i][e[k].j]=e[k].wt;
/which i belongs/ s[e[k].j][e[k].i]=e[k].wt;
}
else
{
if(visited[e[k].i]!=visited[e[k].j])
{
c1=visited[e[k].i];
/merge the two components/ c2=visited[e[k].j];
/into a new single component/ for(l=0;l<n;l++) {
if(visited[l]==c2)
visited[l]=c1;
s[e[k].i][e[k].j]=e[k].wt;
s[e[k].j][e[k].i]=e[k].wt;
}
}
else
printf("\nThe Edge %d TO %d Forms A Circuit\n",e[k].i,e[k].j);
}
}
display_spanning(s,n);
}
/*
main Function
Called By:O.S
Calls:collect_edges(),sort_edges(),form_spanning().
*/
main()
{
int n,g[size][size],i,j,wt,k;
char ans;
clrscr();
printf("\n Enter The Number Of Vertices ");
scanf("%d",&n);
for(i=0;i<7;i++)
for(j=0;j<7;j++)
g[i][j]=0;
do
{
printf("\n Enter The Edge ");
printf("\n i= ");
scanf("%d",&i);
printf("\n j= ");
scanf("%d",&j);
printf("\n Enter The Weight Of The Edge ");
scanf("%d",&wt);
g[i][j]=g[j][i]=wt;
printf("\n Anymore ?");
ans=getch();
}while(ans=='y');
collect_edges(g,n,e);
printf("\n The Number Of Edges In The Graph Are ==> %d",k);
sort_edges(e,k);
form_spanning(e,k,g,n);
getch();
}