Prim’s Algorithm
Prim’s Algorithm
Prim’s algorithm is aused to find minimum spanning tree algorithm that takes a graph as input and this algorithm finds the subset of the edges of that graph which form a tree that includes every vertex and has the minimum sum of weights all the trees that can be formed from the graph
This algorithm begins with the single node and explores all the adjacent nodes with all the connecting edges at each step. The edges with the minimal weights causing no cycles in the graph get selected.
How does the prim’s algorithm work?
Prim’s algorithm is a greedy algorithm that begins from one vertex and continue to add the edges with the smallest weight until the goal is reached.
There are few steps to implement the prims algorithm they are given below:

 Firstly, we have to initialize an minimum spanning tree with the randomly choose vertex.
 Then, we have to find all the edges that connect the tree with the new vertices from the find edges, select the minimum edge and add it to the tree.
 Repeating the step 2 until the minimum spanning tree is formed.
Example of Prim’s algorithm
Start with a weighted graph
Program of prim’s algorithm
#include<stdio.h> #include<stdbool.h> #define INF 9999999 #define V 5 int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; int selected[V]; memset(selected, false, sizeof(selected)); no_edge = 0; selected[0] = true; int x; // row number int y; // col number printf("Edge : Weight\n"); while (no_edge < V  1) { int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } printf("%d  %d : %d\n", x, y, G[x][y]); selected[y] = true; no_edge++; } return 0; }
Output
Edge : Weight 0  1 : 9 1  3 : 19 3  4 : 31 3  2 : 51
The applications of prims algorithm
 Prims algorithm can be used in network designing.
 It can be used to make network cycles.
 It can also be used to lay down electrical wiring cables.
Prims Algorithm Complexity
The time complexity of Prims algorithm is O(E log V)
.
Prims Algorithm Application
 Prim’s algorithm can be used to Laying cables of electrical wiring
 It can be used in network designed
 It can also be used to make protocols in network cycles
Read more, Kruskal’s algorithm