Program is for Kruskal's minimum spanning tree algorithm in C language.

/*

*******************************************************************************

 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();

}

 


Post a Comment

Previous Post Next Post