C Program To Implement Prim’s Algorithm For Minimum Spanning Tree
Learn How To Create a Minimum Spanning Tree using Prim’s Algorithm in C Programming Language. Prim’s Algorithm is a Greedy Algorithm approach that works best by taking the nearest optimum solution.
In the Prim’s Algorithm, every vertex is given a status which is either Temporary or Permanent. Initially all the vertices are temporary and at every step, a temporary vertex is made permanent vertex. The algorithm stops after all the vertices are made permanent.
The temporary vertices are those that have not been included in the Tree whereas the permanent vertices are those that have been included in the tree. Every vertex is associated with a length and predecessor.
What is Minimum Spanning Tree?
A Spanning Tree of a graph G whose sum of the weights is minimum amongst all the spanning trees of G, is called the Minimum Spanning Tree of the graph G.
Must Read: C Program For Warshall’s Algorithm To Find Path Matrix
C Program To Implement Prim’s Algorithm to Find Minimum Spanning Tree
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include<stdio.h> #include<stdlib.h> #define infinity 9999 #define LIMIT 10 #define NIL -1 #define PERMANENT 1 #define TEMPORARY 0 struct edge { int v; int u; }; int n; int predecessor[LIMIT]; int adjacency_matrix[LIMIT][LIMIT]; int length[LIMIT]; int status[LIMIT]; int min_temp(); void new_graph(); void maketree(int root_var, struct edge tree[LIMIT]); int main() { int tree_weight = 0; int count, root; struct edge tree[LIMIT]; new_graph(); printf("\nEnter Root Vertex:\t"); scanf("%d", &root); maketree(root, tree); printf("Enter Edges of the Spanning Tree:\n"); for(count = 1; count <= n - 1; count++) { printf("%d->", tree[count].u); printf("%d\n", tree[count].v); tree_weight = tree_weight + adjacency_matrix[tree[count].u][tree[count].v]; } printf("Spanning Tree Weight:\t%d\n", tree_weight); return 0; } void new_graph() { int count, LIMIT_edges, origin, destination, weight; printf("Enter Number of Vertices:\t"); scanf("%d", &n); LIMIT_edges = n * (n - 1) /2; for(count = 1; count <= LIMIT_edges; count++) { printf("Enter Co- Ordinates of Edge No. %d(-1 -1 to quit):\n",count); printf("Enter Origin Vaue:\t"); scanf("%d", &origin); printf("Enter Destination Vaue:\t"); scanf("%d", &destination); if((origin == -1) && (destination == -1)) { break; } printf("Enter Weight of this Edge:\t"); scanf("%d", &weight); if(destination < 0 || destination >= n || origin < 0 || origin >= n) { printf("Invalid Edge\n"); count--; } else { adjacency_matrix[origin][destination] = weight; adjacency_matrix[destination][origin] = weight; } } } void maketree(int root_var, struct edge tree[LIMIT]) { int current, count; int temp = 0; for(count = 0; count < n; count++) { predecessor[count] = NIL; length[count] = infinity; status[count] = TEMPORARY; } length[root_var] = 0; while(1) { current = min_temp(); if(current == NIL) { if(temp == n - 1) { return; } else { printf("No Spanning Tree is Possible because Graph is disconnected\n"); exit(1); } } status[current] = PERMANENT; if(current != root_var) { count++; tree[temp].u = predecessor[current]; tree[temp].v = current; } for(count = 0; count < n; count++) { if(adjacency_matrix[current][count] > 0 && status[count] == TEMPORARY) { if(adjacency_matrix[current][count] < length[count]) { predecessor[count] = current; length[count] = adjacency_matrix[current][count]; } } } } } int min_temp() { int count; int min = infinity; int x = -1; for(count = 0; count < n; count++) { if(status[count] == TEMPORARY && length[count] < min) { min = length[count]; x = count; } } return x; } |
Must Read: C Program To Solve Producer Consumer Problem
Output
In case you get any Compilation Errors or any doubts in this Code To Make Minimum Spanning Tree using Prim’s Algorithm in C Programming, let us know about it in the Comment Section below. Check this article on GeeksforGeeks for more information on Prims Algorithm.
Awesome code. Finally I found something working.
Is there any similarity between Kruskal’s Algorithm and Prim’s Algorithm?
Both these algorithms can be used to find Minimum Spanning Trees. Apart from this, there are no similarities.
Are there any other algorithms alternative to Prims algorithm to find minimum soanning trees?
i believe that this is a very important interview question.
What is the difference between Prims algorithm and Kruskals algorithm?
To add more to this, the Minimum Spanning Tree or MST, is an application of Disjoint Data Structure.
Awesome codes here. To add more on this, here is a great resource to learn more about Greedy Algorithm – https://www.interviewbit.com/courses/programming/topics/greedy/