Kruskal Algorithm C Program

/*Kruskal Algorithm C Program*/

#include<stdio.h>
#include<conio.h>
#define INFINITY 999
typedef struct Graph
{
int v1,v2,cost;
}GR;
GR G[20];
int tot_edges,tot_nodes;
void create();
void spanning_tree();
int Minimum(int);
void main()
{
clrscr();
printf("\n\t\t graph creation by adjacency matrix");
create();
spanning_tree();
getch();
}
void create()
{
int k;
printf("\n enter total no of nodes:");
scanf("%d",&tot_nodes);
printf("\n enter total no of edges:");
scanf("%d",&tot_edges);
for(k=0;k<tot_edges;k++)
{
 printf("\nenter edges in (v1 v2)form:");
 scanf("%d%d",&G[k].v1,&G[k].v2);
 printf("\n enter corresponding cost=");
 scanf("%d",&G[k].cost);
 }
}
void spanning_tree()
{
 int count,k,v1,v2,i,j,tree[10][10],pos,parent[10],sum;
int Find(int v2,int parent[]);
void Union(int i,int j,int parent[]);
 count=0;
 k=0;
 sum=0;
 for(i=0;i<tot_nodes;i++)
   parent[i]=i;
   while(count!=tot_nodes-1)
   {
    pos=Minimum(tot_edges);
    if(pos==-1)
    {
    break;
    }
    v1=G[pos].v1;
    v2=G[pos].v2;
    i=Find(v1,parent);
    j=Find(v2,parent);
    if(i!=j)
    {
      tree[k][0]=v1;
      tree[k][1]=v2;
      k++;
      count++;
      sum+=G[pos].cost;
      Union(i,j,parent);
    }
    G[pos].cost=INFINITY;

 }
   if(count==tot_nodes-1)
   {
    printf("\n spanning tree is:");
    printf("\n-----------------------------\n");
    for(i=0;i<tot_nodes-1;i++)
    {
      printf("[%d",tree[i][0]);
      printf("-");
      printf("%d",tree[i][1]);
      printf("]");
    }
    printf("\n-------------------------------");
    printf("\n cost of spanning tree=%d",sum);
   }
   else
   {
   printf("\n there is no spanning tree");
   }
 }
 int Minimum(int n)
 {
 int i,small,pos;
 small=INFINITY;
 pos=-1;
 for(i=0;i<n;i++)
 {
    if(G[i].cost<small)
    {
    small=G[i].cost;
    pos=i;
    }
 }
 return pos;
 }
 int Find(int v2,int parent[])
 {
 while(parent[v2]!=v2)
 {
   v2=parent[v2];
   }
   return v2;
 }
 void Union(int i,int j,int parent[])
 {
   if(i<j)
   {
     parent[j]=i;
   }
   else
   {
   parent[i]=j;
   }
 }
o/p-

                 graph creation by adjacency matrix

 enter total no of nodes:6

 enter total no of edges:10

enter edges in (v1 v2)form:1

2

 enter corresponding cost=10

enter edges in (v1 v2)form:2

3

 enter corresponding cost=50

enter edges in (v1 v2)form:3

6

 enter corresponding cost=15

enter edges in (v1 v2)form:6 4

 enter corresponding cost=20

enter edges in (v1 v2)form:4 1

 enter corresponding cost=30

enter edges in (v1 v2)form:1 5

 enter corresponding cost=45

enter edges in (v1 v2)form:5 2

 enter corresponding cost=40

enter edges in (v1 v2)form:5 3

 enter corresponding cost=35

enter edges in (v1 v2)form:5 6

 enter corresponding cost=55

enter edges in (v1 v2)form:6 2

 enter corresponding cost=25

 spanning tree is:

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

[1-2][3-6][6-4][6-2][5-3]

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

 cost of spanning tree=105