# Minimum Spanning trees Prim’s Algorithm

*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).
*

*Prim’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:*

*Select a vertex from the graph, and add it to set S , S will be empty initially.**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.**Add the nearest vertex to the set S.*

*Repeat steps 2 and 3 until Set S includes every vertex in graph.*

*Minimum Spanning trees Prim’s Algorithm c ++ code*

*Minimum 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

## Leave a Reply