SHARE
TWEET

Untitled

a guest Dec 8th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define V 5
  6.  
  7.  
  8. int minkey(int key[],bool mstSet[])
  9. {
  10.     int min = INT_MAX,min_index;
  11.     for(int i=0;i<V;i++)
  12.     {
  13.         if(mstSet[i]==false && min>key[i])
  14.         {
  15.             min = key[i],min_index = i ;
  16.         }
  17.     }
  18.     return min_index;
  19. }
  20.  
  21. void printPrims(int parent[],int graph[V][V])
  22. {
  23.     cout << "PARENT \tWEIGHT" << endl;
  24.     for(int i=1;i<V;i++)
  25.     {
  26.         cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl ;
  27.     }
  28. }
  29.  
  30. void primMst(int graph[V][V])
  31. {
  32.     int key[V] ;
  33.     int parent[V] ;
  34.     bool mstSet[V] ;
  35.     for(int i=0;i<V;i++)
  36.     {
  37.       key[i] = INT_MAX,mstSet[i]= false ;
  38.     }
  39.     key[0]=0;
  40.     parent[0]= -1 ;
  41.     for(int count =0;count<V-1;count++)
  42.     {
  43.         int u = minkey(key,mstSet);
  44.         mstSet[u]=true;
  45.         for(int v=0;v<V;v++)
  46.         {
  47.             if(mstSet[v]==false && graph[u][v] && key[v]>graph[u][v])
  48.             {
  49.                 key[v] = graph[u][v],parent[v] = u ;
  50.             }
  51.         }
  52.     }
  53.     printPrims(parent,graph);
  54. }
  55.  
  56. int main()
  57. {
  58.     /* Let us create the following graph
  59.         2 3
  60.     (0)--(1)--(2)
  61.     | / \ |
  62.     6| 8/ \5 |7
  63.     | / \ |
  64.     (3)-------(4)
  65.             9     */
  66.     int graph[V][V] = { { 0, 2, 0, 6, 0 },
  67.                         { 2, 0, 3, 8, 5 },
  68.                         { 0, 3, 0, 0, 7 },
  69.                         { 6, 8, 0, 0, 9 },
  70.                         { 0, 5, 7, 9, 0 } };
  71.  
  72.     // Print the solution
  73.     primMst(graph);
  74.  
  75.     return 0;
  76. }
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