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)
Press return to continue

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

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.