Kruskal Algorithm

1:  #include<stdio.h>  
2:  #include<conio.h>  
3:  int i, parent[10],t[20][2],mincost,k,ne;  
4:  struct edge  
5:  {  
6:  int u,v,c;  
7:  }e[20],temp;  
8:  swap(struct edge *p, struct edge *q)  
9:  {  
10:  temp=*p;  
11:  *p=*q;  
12:  *q=temp;  
13:  return;  
14:  }  
15:  int find(int c)  
16:  {  
17:  while(parent[c]>=0)  
18:  c=parent[c];  
19:  return c;  
20:  }  
21:  unionn(int x,int y)  
22:  {  
23:  parent[x]=y;  
24:  return;  
25:  }  
26:  void main()  
27:  {  
28:  int n, ch, j,k,a,b,ed,cycles;  
29:  clrscr();  
30:  printf("enter how many vertices:");  
31:  scanf("%d", &n);  
32:  printf("enter how many edges:");  
33:  scanf("%d", &ed);  
34:  printf("enter the edges and their costs...\n");  
35:  printf("\tfrom\tto\tcost\n");  
36:  for(i=1;i<=ed;i++)  
37:  {  
38:  printf("\t");  
39:  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);  
40:  }  
41:  i--;  
42:  for(j=1;j<i;j++)  
43:  {  
44:  for(k=j+1;k<=i;k++)  
45:  if(e[k].c<e[j].c)  
46:  swap(&e[j],&e[k]);  
47:  }  
48:  for(j=1;j<=n;j++)  
49:  parent[j]=-1;  
50:  mincost=0;  
51:  k=ne=0;  
52:  cycles=0;  
53:  while((k<n-1)&&(ne<=i))  
54:  {  
55:  ne++;  
56:  a=find(e[ne].u);  
57:  b=find(e[ne].v);  
58:  if(a!=b)  
59:  {  
60:       k++;  
61:       t[k][1]=e[ne].u;  
62:       t[k][2]=e[ne].v;  
63:       mincost=mincost+e[ne].c;  
64:       unionn(a,b);  
65:  }  
66:  }  
67:  if(k!=n-1)  
68:  printf("\n no spanning tree");  
69:  else  
70:  {  
71:  printf("\n the edges in the min cost spanning tree....\n");  
72:  for(k=1;k<=n;k++)  
73:  printf("%d-->%d\n",t[k][1],t[k][2]);  
74:  printf("\n the min cost=%d",mincost);  
75:  }  
76:  getch();  
77:  }