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.

 

 

 

 

 

 

 

Read more, Kruskal’s algorithm