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

Prim's algorithm

Start with a weighted graph


Prim's algorithm
Choose a vertex


Prim's algorithm
Choose the shortest edge from this vertex and added it


Prim's algorithm
Choose the nearest vertex not  in the solution


Prim's algorithm
Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at random


Prim's algorithm
Repeat until have a spanning tree.


Program of prim’s algorithm


#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;

  return 0;



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

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *