SHARE
TWEET

Final Prims

naeem043 Aug 3rd, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. int p[9],k[9],t[9],i,j,h_cost=0;
  4. int g[9][9] = {
  5.     {0,4,0,0,0,0,0,8,0},
  6.     {4,0,8,0,0,0,0,11,0},
  7.     {0,8,0,7,0,4,0,0,2},
  8.     {0,0,7,0,9,14,0,0,0},
  9.     {0,0,0,9,0,10,0,0,0},
  10.     {0,0,4,14,10,0,2,0,0},
  11.     {0,0,0,0,0,2,0,1,6},
  12.     {8,11,0,0,0,0,1,0,7},
  13.     {0,0,2,0,0,0,6,7,0},
  14.  
  15. };
  16.  
  17. int Find_min()
  18. {
  19.     int m = 999999,index;
  20.     for(i=0;i<9;i++)
  21.     {
  22.         if(k[i]<m && t[i] == 0)
  23.         {
  24.             m = k[i];
  25.             index = i;
  26.         }
  27.     }
  28.  
  29.     return index;
  30. }
  31.  
  32. void Print_Path(int g[9][9], int node, int v)
  33. {
  34.     if(v==node) printf("Source");
  35.    else if(p[v]==-1) printf("0 ");
  36.    else
  37.         {
  38.             Print_Path(g,7,p[v]);
  39.             printf("%d ", v);
  40.             h_cost += k[v];
  41.         }
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47.     int u,cost=0;
  48.  
  49.  
  50.     for(i=0;i<9;i++)
  51.     {
  52.         for(j=0;j<9;j++)
  53.             printf("%d\t", g[i][j]);
  54.         printf("\n");
  55.     }
  56.  
  57.    for(i=0;i<9;i++)
  58.     {
  59.         p[i] = -1;
  60.         k[i] = 999999;
  61.         t[i] = 0;
  62.  
  63.     }
  64.     k[0] = 0;
  65.  
  66.   for(j=0;j<9;j++)
  67.     {
  68.         u = Find_min();
  69.         t[u] = 1;
  70.         for(i=0;i<9;i++)
  71.         {
  72.             if(g[u][i] < k[i] && g[u][i] !=0 && t[i] != 1)
  73.             {
  74.                 p[i] = u;
  75.                 k[i] = g[u][i];
  76.             }
  77.         }
  78.     }
  79.  
  80.  
  81.     printf("\n Parent:\t\t\t");
  82.     for(i=0;i<9;i++)
  83.         printf("%d\t",p[i]);
  84.  
  85.  
  86.     printf("\n Key Value:\t\t\t");
  87.     for(i=0;i<9;i++)
  88.     {
  89.         printf("%d\t",k[i]);
  90.         cost += k[i];
  91.     }
  92.  
  93.  
  94.     printf("\n Tree Status:\t\t\t");
  95.     for(i=0;i<9;i++)
  96.         printf("%d\t",t[i]);
  97.  
  98.     printf("\n Total Cost:\t %d\n",cost);
  99.  
  100.     printf("\n Path from (a-h):\t");
  101.  
  102.     int source=0,des=8;
  103.     Print_Path(g,source,des);
  104.     printf("\n Total Cost of (a-h):\t %d",h_cost);
  105.  
  106.     return 0;
  107. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top