Advertisement
naeem043

C Prim's Algorithm

Jun 22nd, 2018
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.45 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. int p[9],k[9],t[9],i,j;
  6. int g[9][9] = {
  7.     {0,4,0,0,0,0,0,8,0},
  8.     {4,0,8,0,0,0,0,11,0},
  9.     {0,8,0,7,0,4,0,0,2},
  10.     {0,0,7,0,9,14,0,0,0},
  11.     {0,0,0,9,0,10,0,0,0},
  12.     {0,0,4,14,10,0,2,0,0},
  13.     {0,0,0,0,0,2,0,1,6},
  14.     {8,11,0,0,0,0,1,0,7},
  15.     {0,0,2,0,0,0,6,7,0},
  16.  
  17. };
  18.  
  19. int Find_min()
  20. {
  21.     int m = 999999,index;
  22.     for(i=0;i<9;i++)
  23.     {
  24.         if(k[i]<m && t[i] == 0)
  25.         {
  26.             m = k[i];
  27.             index = i;
  28.         }
  29.     }
  30.  
  31.     return index;
  32. }
  33.  
  34. int main()
  35. {
  36.     int u,cost=0;
  37.     for(i=0;i<9;i++)
  38.     {
  39.         for(j=0;j<9;j++)
  40.             printf("%d\t", g[i][j]);
  41.         printf("\n");
  42.     }
  43.  
  44.    for(i=0;i<9;i++)
  45.     {
  46.         p[i] = -1;
  47.         k[i] = 999999;
  48.         t[i] = 0;
  49.  
  50.     }
  51.     k[0] = 0;
  52.  
  53.   for(j=0;j<9;j++)
  54.     {
  55.         u = Find_min();
  56.         t[u] = 1;
  57.         for(i=0;i<9;i++)
  58.         {
  59.             if(g[u][i] < k[i] && g[u][i] !=0 && t[i] != 1)
  60.             {
  61.                 p[i] = u;
  62.                 k[i] = g[u][i];
  63.             }
  64.         }
  65.     }
  66.  
  67.  
  68.     printf("\n Parent:\t\t\t");
  69.     for(i=0;i<9;i++)
  70.         printf("%d\t",p[i]);
  71.  
  72.  
  73.     printf("\n Key Value:\t\t\t");
  74.     for(i=0;i<9;i++)
  75.     {
  76.         printf("%d\t",k[i]);
  77.         cost += k[i];
  78.     }
  79.  
  80.  
  81.     printf("\n Tree Status:\t\t\t");
  82.     for(i=0;i<9;i++)
  83.         printf("%d\t",t[i]);
  84.  
  85.     printf("\n Total Cost:\t %d",cost);
  86.  
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement