Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define VAL 999
- int i,j,k,a,b,u,v,n,ne=1;
- int min,mincost=0,cost[20][20],parent[9];
- // union - find
- int find(int i)
- {
- while(parent[i])
- i=parent[i];
- return i;
- }
- int uni(int i,int j)
- {
- if(i!=j)
- {
- parent[j]=i;
- return 1;
- }
- return 0;
- }
- int main()
- {
- printf("Implementation of Kruskal's algorithm\n");
- printf("Enter the no. of vertices:");
- scanf("%d",&n);
- printf("Enter the cost adjacency matrix:\n");
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- printf("node %d to node %d: ",i,j);
- scanf("%d",&cost[i][j]);
- if(cost[i][j]==0)
- cost[i][j]=VAL;
- }
- }
- printf("The edges of Minimum Cost Spanning Tree are\n");
- while(ne < n)
- {
- for(i=1,min=VAL;i<=n;i++)
- {
- for(j=1;j <= n;j++)
- {
- if(cost[i][j] < min)
- {
- min=cost[i][j];
- a=u=i;
- b=v=j;
- }
- }
- }
- u=find(u);
- v=find(v);
- if(uni(u,v))
- {
- // printing edges
- printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
- mincost +=min;
- }
- cost[a][b]=cost[b][a]=999;
- }
- // minimum cost
- printf("\n\tMinimum cost = %d\n",mincost);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement