# C++ Program to Apply the Prim’s Algorithm to Find the Minimum Spanning Tree of a Graph

This is a C++ Program to find the minimum spanning tree of the given graph using Prims algorihtm. In computer science, Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Here is source code of the C++ Program to Apply the Prim’s Algorithm to Find the Minimum Spanning Tree of a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. `#include <limits.h>`
3. `#include <iostream>`
4. ` `
5. `using namespace std;`
6. ` `
7. `// Number of vertices in the graph`
8. `#define V 5`
9. ` `
10. `// A utility function to find the vertex with minimum key value, from`
11. `// the set of vertices not yet included in MST`
12. `int minKey(int key[], bool mstSet[])`
13. `{`
14. `    // Initialize min value`
15. `    int min = INT_MAX, min_index;`
16. ` `
17. `    for (int v = 0; v < V; v++)`
18. `    if (mstSet[v] == false && key[v] < min)`
19. `    min = key[v], min_index = v;`
20. ` `
21. `    return min_index;`
22. `}`
23. ` `
24. `// A utility function to print the constructed MST stored in parent[]`
25. `int printMST(int parent[], int n, int graph[V][V])`
26. `{`
27. `    cout<<"Edge   Weight\n";`
28. `    for (int i = 1; i < V; i++)`
29. `        printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);`
30. `}`
31. ` `
32. `// Function to construct and print MST for a graph represented using adjacency`
33. `// matrix representation`
34. `void primMST(int graph[V][V])`
35. `{`
36. `    int parent[V]; // Array to store constructed MST`
37. `    int key[V]; // Key values used to pick minimum weight edge in cut`
38. `    bool mstSet[V]; // To represent set of vertices not yet included in MST`
39. ` `
40. `    // Initialize all keys as INFINITE`
41. `    for (int i = 0; i < V; i++)`
42. `        key[i] = INT_MAX, mstSet[i] = false;`
43. ` `
44. `    // Always include first 1st vertex in MST.`
45. `    key[0] = 0; // Make key 0 so that this vertex is picked as first vertex`
46. `    parent[0] = -1; // First node is always root of MST`
47. ` `
48. `    // The MST will have V vertices`
49. `    for (int count = 0; count < V - 1; count++)`
50. `    {`
51. `        // Pick thd minimum key vertex from the set of vertices`
52. `        // not yet included in MST`
53. `        int u = minKey(key, mstSet);`
54. ` `
55. `        // Add the picked vertex to the MST Set`
56. `        mstSet[u] = true;`
57. ` `
58. `        // Update key value and parent index of the adjacent vertices of`
59. `        // the picked vertex. Consider only those vertices which are not yet`
60. `        // included in MST`
61. `        for (int v = 0; v < V; v++)`
62. ` `
63. `            // graph[u][v] is non zero only for adjacent vertices of m`
64. `            // mstSet[v] is false for vertices not yet included in MST`
65. `            // Update the key only if graph[u][v] is smaller than key[v]`
66. `            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])`
67. `                parent[v] = u, key[v] = graph[u][v];`
68. `    }`
69. ` `
70. `    // print the constructed MST`
71. `    printMST(parent, V, graph);`
72. `}`
73. ` `
74. `// driver program to test above function`
75. `int main()`
76. `{`
77. `    /* Let us create the following graph`
78. `     2    3`
79. `     (0)--(1)--(2)`
80. `     |   / \   |`
81. `     6| 8/   \5 |7`
82. `     | /     \ |`
83. `     (3)-------(4)`
84. `     9          */`
85. `    int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 },`
86. `            { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 }, };`
87. ` `
88. `    // Print the solution`
89. `    primMST(graph);`
90. ` `
91. `    return 0;`
92. `}`

Output:

```\$ g++ PrimsMST.cpp
\$ a.out

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.