Algorithm Prima

Дерево, Алгоритм, Tree

Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds a subset of the edges of that graph that forms a tree that includes each vertex and also has the minimum sum of weights among all trees that can be formed from the graph.

How Prim's algorithm works

It falls under a class of algorithms called "greedy" algorithms that find a local optimum in the hope of finding a global optimum.

We start at one vertex and keep adding edges with the lowest weight until we reach our goal.

The steps to implement Prim's algorithm are as follows:

1. Initialize a minimum spanning tree with an arbitrary vertex.
2. Find all edges that connect the tree to new vertices, find the minimum and add it to the tree.
3. Keep repeating step 2 until you get the minimum spanning tree.

Prima algorithm example

Prim's algorithm. Pseudocode.

The pseudocode for Prim's algorithm shows how we create two sets of vertices U and VU. U contains a list of vertices that have been visited, and VU a list of vertices that have not been visited. One by one, we move vertices from set VU to set U, connecting the edge with the lowest weight.

Implementing Prim's Algorithm in C++

The program below implements Prim's algorithm in C++. Although it uses an adjacency matrix to represent the graph, this algorithm can also be implemented using an adjacency list to improve its efficiency.

#include <iostream>
#include <cstring>
using namespace std;
 
#define INF 9999999
 
// number of vertices in grapj
#define V 5
 
// create a 2d array of size 5x5
//for adjacency matrix to represent graph
 
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;            // number of edge
 
  // create a array to track selected vertex
  // selected will become true otherwise false
  int selected[V];
 
 // set selected false initially
  memset (selected, false, sizeof (selected));
 
 // set number of edge to 0
  no_edge = 0;
 
  // the number of egde in minimum spanning tree will be
  // always less than (V -1), where V is number of vertices in
  //graph
 
  // choose 0th vertex and make it true
  selected[0] = true;
 
  int x;            //  row number
  int y;            //  col number
 
  // print for edge and weight
  cout << "Edge" << " : " << "Weight";
  cout << endl;
  while (no_edge < V - 1) {
 
  //For every vertex in the set S, find the all adjacent vertices
  // , calculate the distance from the vertex selected at step 1.
  // if the vertex is already in the set S, discard it otherwise
  //choose another vertex nearest to selected vertex  at step 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]) { // not in selected and there is an edge
                  if (min > G[i][j]) {
                      min = G[i][j];
                      x = i;
                      y = j;
                  }
 
              }
          }
        }
      }
      cout << x <<  " - " << y << " :  " << G[x][y];
      cout << endl;
      selected[y] = true;
      no_edge++;
    }
 
  return 0;
}

When we run the above code, we get output like this:

Edge : Weight
0 - 1 :  9
1 - 3 :  19
3 - 4 :  31
3 - 2 :  51

Prim's algorithm vs Kraskal's

Kruskal's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the MST graph. Instead of starting at the top, Kruskal's algorithm sorts all edges from low weight to high weight and continues adding the lowest edges, ignoring those edges that create a loop.