minimum spanning tree definition: What is minimum spanning tree

Minimum Spanning trees Prim’s Algorithm. A minimum spanning tree of a connected undirected graph is a tree which connects all the vertices and sum of weights of all the edges of minimum spanning tree is smallest compare to all other trees in a given graph. Let us find out the minimum spanning tree based on Prim’s algorithm in below graph. ( snapshot from :http://www.comp.nus.edu.sg/~stevenha/visualization/mst.html).

Minimum Spanning trees Prim's AlgorithmPrim’s algorithm is  a greedy  algorithm. we can see that in the let side the minimum spanning tree has less than (n -1) edges.

The Prim’s algorithm greedily construct  the minimal spanning tree with below steps:

  1. Select a vertex from the graph, and add it to set S , S will be empty initially.
  2. 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.
  3. Add the nearest vertex to the set S.
  4. Repeat steps 2 and 3 until Set S includes every vertex in graph.

confMinimum Spanning trees Prim’s Algorithm c ++ code

#include <iostream>
#include<string.h>
using namespace std;

// define some large value and assume it to be
// infinity

#define INF 9999999

// create a adjacency matrix
// to represent the graph

// define number of vertex
#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 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
		    {
		      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;
}

The complexity of above code for prim’s algorithm is O(N²), where N is number of vertex. if we use adjacency list for graph then complexity reduced to O(|E| log |V|).

Ref:http://wiki.roblox.com/index.php?title=Prim%27s_Algorithm



Related Contents to follow