nkb29597

Krushkal's Algorithm

Oct 22nd, 2019
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.68 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<limits.h>
  4. #define V 5
  5. int parent[V];
  6. int find(int i)
  7. {
  8.     while(parent[i])
  9.         i = parent[i];
  10.     return i;
  11. }
  12. int uni(int i,int j)
  13. {
  14.     if(i!=j)
  15.     {
  16.         parent[j] = i;
  17.         return 1;
  18.     }
  19.     return 0;
  20. }
  21. void main()
  22. {
  23.     /* Let us create the following graph
  24.         2    3
  25.     (0)--(1)--(2)
  26.     |   /   \   |
  27.    6| 8/     \5 |7
  28.     | /       \ |
  29.     (3)-------(4)
  30.           9*/
  31.     int cost[V][V] = {{0, 2, 0, 6, 0},
  32.                       {2, 0, 3, 8, 5},
  33.                       {0, 3, 0, 0, 7},
  34.                       {6, 8, 0, 0, 9},
  35.                       {0, 5, 7, 9, 0},
  36.                      };
  37.     /*int cost[V][V] = {{0,4,0,6,0},
  38.                       {4,0,3,2,5},
  39.                       {0,3,0,0,6},
  40.                       {6,2,0,0,7},
  41.                       {0,5,6,7,0}};*/
  42.     int i,j,a,b,u,v,ne=1, mini, mincost=0;
  43.     for(i=0;i<V;i++)
  44.         for(j=0;j<V;j++)
  45.             if(cost[i][j]==0)
  46.                 cost[i][j]=INT_MAX;
  47.     printf("The edges of Minimum Cost Spanning Tree are\n");
  48.     while(ne < V)
  49.     { mini=INT_MAX;
  50.         for(i=0;i<V;i++)
  51.         {
  52.              for(j=0;j<V;j++)
  53.             {
  54.                 if(cost[i][j] < mini)
  55.                 {
  56.                     mini = cost[i][j];
  57.                     a = u = i;
  58.                     b = v = j;
  59.                 }
  60.             }
  61.         }
  62.         u=find(u);
  63.         v=find(v);
  64.         if(uni(u,v))
  65.         {
  66.             printf("%d edge (%d,%d) =%d\n",ne++,a,b,mini);
  67.             mincost += mini;
  68.         }
  69.         cost[a][b] = cost[b][a] = INT_MAX;
  70.     }//end of while
  71.     printf("\nMinimum cost = %d\n",mincost);
  72. }
Advertisement
Add Comment
Please, Sign In to add comment