## Minimum Spanning Tree using Prim’s Algorithm

Write a C Program for Creating Minimum Spanning Tree using Prim’s Algorithm. Here’s simple Program for minimum cost spanning tree using prim’s algorithm example in C Programming Language.

*Prim’s Algorithm*

*Prim’s Algorithm*

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.

This algorithm is directly based on the MST( minimum spanning tree) property.

** How does Prim’s Algorithm Work?** The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a

*Spanning*Tree. And they must be connected with the minimum weight edge to make it a

*Minimum*Spanning Tree.

The * steps for implementing* Prim’s algorithm are as follows:

- Initialize the minimum spanning tree with a vertex chosen at random.
- Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
- Keep repeating step 2 until we get a minimum spanning tree

**Also Read : : C Program to find Shortest Path Matrix by Modified Warshall’s Algorithm**

Below is the source code for C Program for Creating Minimum Spanning Tree using Prim’s Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :

**SOURCE CODE : :**

**SOURCE CODE : :**

/* C Program for Creating Minimum Spanning Tree using Prim's Algorithm */ #include<stdio.h> #include<stdlib.h> #define MAX 10 #define TEMP 0 #define PERM 1 #define infinity 9999 #define NIL -1 struct edge { int u; int v; }; int n; int adj[MAX][MAX]; int predecessor[MAX]; int status[MAX]; int length[MAX]; void create_graph(); void maketree(int r, struct edge tree[MAX]); int min_temp(); int main() { int wt_tree = 0; int i, root; struct edge tree[MAX]; create_graph(); printf("\nEnter root vertex : "); scanf("%d",&root); maketree(root, tree); printf("\nEdges to be included in spanning tree are : \n"); for(i=1; i<=n-1; i++) { printf("%d-> ",tree[i].u); printf("%d\n",tree[i].v); wt_tree += adj[tree[i].u][tree[i].v]; } printf("\nWeight of spanning tree is : %d\n", wt_tree); return 0; }/*End of main()*/ void maketree(int r, struct edge tree[MAX]) { int current,i; int count = 0;/*number of vertices in the tree*/ /*Initialize all vertices*/ for(i=0; i<n; i++) { predecessor[i] = NIL; length[i] = infinity; status[i] = TEMP; } /*Make length of root vertex 0*/ length[r] = 0; while(1) { /*Search for temporary vertex with minimum length and make it current vertex*/ current = min_temp(); if(current == NIL) { if(count == n-1) /*No temporary vertex left*/ return; else /*Temporary vertices left with length infinity*/ { printf("\nGraph is not connected, No spanning tree possible\n"); exit(1); } } /*Make the current vertex permanent*/ status[current] = PERM; /*Insert the edge ( predecessor[current], current) into the tree, except when the current vertex is root*/ if(current != r) { count++; tree[count].u = predecessor[current]; tree[count].v = current; } for(i=0; i<n; i++) if(adj[current][i] > 0 && status[i] == TEMP) if(adj[current][i] < length[i]) { predecessor[i] = current; length[i] = adj[current][i]; } } }/*End of make_tree( )*/ /*Returns the temporary vertex with minimum value of length Returns NIL if no temporary vertex left or all temporary vertices left have pathLength infinity*/ int min_temp() { int i; int min = infinity; int k = -1; for(i=0; i<n; i++) { if(status[i] == TEMP && length[i] < min) { min = length[i]; k = i; } } return k; }/*End of min_temp()*/ void create_graph() { int i,max_edges,origin,destin,wt; printf("\nEnter number of vertices : "); scanf("%d",&n); max_edges = n*(n-1)/2; for(i=1; i<=max_edges; i++) { printf("\nEnter edge %d(-1 -1 to quit) : ",i); scanf("%d %d",&origin,&destin); if((origin == -1) && (destin == -1)) break; printf("\nEnter weight for this edge : "); scanf("%d",&wt); if( origin >= n || destin >= n || origin < 0 || destin < 0) { printf("\nInvalid edge!\n"); i--; } else { adj[origin][destin] = wt; adj[destin][origin] = wt; } } }

**OUTPUT : :**

**OUTPUT : :**

/* C Program for Creating Minimum Spanning Tree using Prim's Algorithm */ Enter number of vertices : 5 Enter edge 1(-1 -1 to quit) : 0 1 Enter weight for this edge : 2 Enter edge 2(-1 -1 to quit) : 0 2 Enter weight for this edge : 4 Enter edge 3(-1 -1 to quit) : 0 3 Enter weight for this edge : 1 Enter edge 4(-1 -1 to quit) : 0 4 Enter weight for this edge : 2 Enter edge 5(-1 -1 to quit) : 1 3 Enter weight for this edge : 3 Enter edge 6(-1 -1 to quit) : 2 3 Enter weight for this edge : 1 Enter edge 7(-1 -1 to quit) : 1 4 Enter weight for this edge : 2 Enter edge 8(-1 -1 to quit) : 3 4 Enter weight for this edge : 2 Enter edge 9(-1 -1 to quit) : -1 -1 Enter root vertex : 0 Edges to be included in spanning tree are : 0-> 3 3-> 2 0-> 1 0-> 4 Weight of spanning tree is : 6 Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may * Contact Us* through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

**Thanks for reading the post…**

**Recommended Posts : :**

**Recommended Posts : :**

- Shortest Path Matrix by Modified Warshall’s Algorithm
- Path Matrix by Warshall’s Algorithm
- Path Matrix by powers of Adjacency matrix
- Program for Creation of Adjacency Matrix
- Shortest Path using Bellman Ford Algorithm