Advertisement
Sheyshya

minimum spanning

Aug 13th, 2019
295
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.43 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define VAL 999
  5. int i,j,k,a,b,u,v,n,ne=1;
  6. int min,mincost=0,cost[20][20],parent[9];
  7. // union - find
  8. int find(int i)
  9. {
  10.     while(parent[i])
  11.     i=parent[i];
  12.     return i;
  13. }
  14. int uni(int i,int j)
  15. {
  16.     if(i!=j)
  17.     {
  18.         parent[j]=i;
  19.         return 1;
  20.     }
  21.     return 0;
  22. }
  23. int main()
  24. {
  25.     printf("Implementation of Kruskal's algorithm\n");
  26.     printf("Enter the no. of vertices:");
  27.     scanf("%d",&n);
  28.     printf("Enter the cost adjacency matrix:\n");
  29.     for(i=1;i<=n;i++)
  30.     {
  31.         for(j=1;j<=n;j++)
  32.         {
  33.             printf("node %d to node %d: ",i,j);
  34.             scanf("%d",&cost[i][j]);
  35.             if(cost[i][j]==0)
  36.                 cost[i][j]=VAL;
  37.         }
  38.     }
  39.     printf("The edges of Minimum Cost Spanning Tree are\n");
  40.     while(ne < n)
  41.     {
  42.         for(i=1,min=VAL;i<=n;i++)
  43.         {
  44.             for(j=1;j <= n;j++)
  45.             {
  46.                 if(cost[i][j] < min)
  47.                 {
  48.                     min=cost[i][j];
  49.                     a=u=i;
  50.                     b=v=j;
  51.                 }
  52.             }
  53.         }
  54.         u=find(u);
  55.         v=find(v);
  56.         if(uni(u,v))
  57.         {
  58.             // printing edges
  59.             printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
  60.             mincost +=min;
  61.         }
  62.         cost[a][b]=cost[b][a]=999;
  63.     }
  64.     // minimum cost
  65.     printf("\n\tMinimum cost = %d\n",mincost);
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement