C Program to Find Minimum Spanning Tree using Prim’s Algorithm

This is a C Program to find the minimum spanning tree of the given graph using Prims algorihtm. Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
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.  
  4. #define V 5
  5.  
  6. int minKey(int key[], int mstSet[]) {
  7.     int min = INT_MAX, min_index;
  8.     int v;
  9.     for (v = 0; v < V; v++)
  10.         if (mstSet[v] == 0 && key[v] < min)
  11.             min = key[v], min_index = v;
  12.  
  13.     return min_index;
  14. }
  15.  
  16. int printMST(int parent[], int n, int graph[V][V]) {
  17.     int i;
  18.     printf("Edge   Weight\n");
  19.     for (i = 1; i < V; i++)
  20.         printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
  21. }
  22.  
  23. void primMST(int graph[V][V]) {
  24.     int parent[V]; // Array to store constructed MST
  25.     int key[V], i, v, count; // Key values used to pick minimum weight edge in cut
  26.     int mstSet[V]; // To represent set of vertices not yet included in MST
  27.  
  28.     // Initialize all keys as INFINITE
  29.     for (i = 0; i < V; i++)
  30.         key[i] = INT_MAX, mstSet[i] = 0;
  31.  
  32.     // Always include first 1st vertex in MST.
  33.     key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
  34.     parent[0] = -1; // First node is always root of MST
  35.  
  36.     // The MST will have V vertices
  37.     for (count = 0; count < V - 1; count++) {
  38.         int u = minKey(key, mstSet);
  39.         mstSet[u] = 1;
  40.  
  41.         for (v = 0; v < V; v++)
  42.  
  43.             if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
  44.                 parent[v] = u, key[v] = graph[u][v];
  45.     }
  46.  
  47.     // print the constructed MST
  48.     printMST(parent, V, graph);
  49. }
  50.  
  51. int main() {
  52.     /* Let us create the following graph
  53.      2    3
  54.     (0)--(1)--(2)
  55.      |   / \   |
  56.     6| 8/   \5 |7
  57.      | /     \ |
  58.     (3)-------(4)
  59.      9          */
  60.     int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 },
  61.             { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 }, };
  62.  
  63.     primMST(graph);
  64.  
  65.     return 0;
  66. }

Output:

$ gcc PrimsMST.c
$ ./a.out
 
Edge   Weight
0 - 1    2 
1 - 2    3 
0 - 3    6 
1 - 4    5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.