Guest User

Untitled

a guest
Dec 8th, 2019
81
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