Objective of prim’s algorithm is to understand the Greedy method to obtain a minimum cost spanning tree edge by edge.

Greedy method :

  1. It is the most straight forward design technique. Most of the problems have n inputs & require us to obtain a subset that satisfies some constraints.

  2. Any subset that satisfies these constraints is called a feasible solution.

  3. We find a feasible solution that either maximizes or minimizes a given objective function.

  4. A feasible solution that does this is called an ‘Optimal Solution’ .

Greedy algorithm :

· It works in stages , considers one input at a time .

· Inputs are considered in an order determined by some selection procedure.

· At each stage, decision is made regarding whether a particular input is in optimal solution.

· Inclusion of next input into partially constructed optimal solution should always result into feasible solution. If not then, this input is not considered.

· Selection procedure is based on some optimization measure; which may be objective function.

· Greedy algorithm that makes use of optimization measures to generate suboptimal solution is called ‘Subset Paradigm’.

General greedy algorithm :

Algorithm Greedy (a,n)

// a[1…n] contains n inputs.

{

solution=0; //initialise the solution

for( i=1 to n )

do

{

x= select(a);

if(feasible(solution, x)) then

solution= union(solution , x);

}

return solution;

}

à Function select , selects an input from a[ ] and removes it. The selected input’s value is assigned to x.

àFunction feasible is Boolean valued function that determines whether x can be included into solution vector.

àFunction union combines x with solution and updates the objective function.

· Knapsack problem , job sequencing , minimum spanning trees comes under the subset paradigm.

· Shortest path , Huffman codes comes under ordering paradigm.

Minimum cost spanning trees :

Definition : Spanning trees –

Let G = (V , E) be an undirected connected graph. A subgraph t= ( V , E’) of G is a spanning tree if and only if t is a tree. (No cycle exists.)


In practical situations, the edges have weights assigned to them, weights are positive. These weights may represent the cost of construction, lengths of links etc.

Given such weighted graph one would like to select cities (vertices) to have minimum total cost / minimum total length. So one can find a spanning tree with minimum cost.

Since identification of minimum spanning tree involves selection of a subset of the edges, this problem fits into the Subset Paradigm.

Prims algorithm’s outline :

Greedy method constructs the tree by including edge by edge. Choose an edge that results in a minimum increase in sum of cost of edges so far included. Also set of edges so far selected form a tree. (No cycle.)

Pseudo code for Prim’s algorithm :

Prim()

// cost[1..n][1..] is a cost adjacency matrix.

// n: number of vertices in the graph.

// cost [ i ][ j ] =∞ , if there is no edge between I and j.

// cost [ i ][ j ] =∞ , if i=j

// cost [ i ][ j ] = cost [ i ][ j ] = positive number if it is edge.

// t [1..n-1][1..2] has all the edges of minimum spanning tree

// mincost is minimum cost

// near[ ] is an array which stores vertex in tree

// such that cost [ j ][ near[ j ] ] is minimum among all choices for near[ j ].

  1. mincost =0;

  2. For (i=2 to n) do near[ i ]=1;

  3. Near[1]=0 //vertex 1 is initially in ‘t’ .

  4. For(i=1 to n-1) do

  5. { // find n-1 edges of tree.

  6. Let j be an index such that

  7. Near[ j ] !=0 & cost[ j ][ near[ j ] ] is minimum.

  8. // computation of j requires linear loop

  9. // not shown above.

  10. t[ i ][1] = j; t[ i ][2]= near[ j ];

  11. mincost=mincost + cost[ j ][near [ j ] ];

  12. Near[ j ] =0;

  13. For( k= 1 to n ) do //update near[ ]

  14. If(near[ k ] !=0) && (cost[ k ][ near[ k ] ] > cost[ k ][ j ])

  15. Near[ k ]=j;

  16. }

  17. return mincost.

Stages in Prim’s algorithm :

Complexity : The time required by algorithm Prim is O(n^2) where n is number of vertices in graph G. Each iteration of for loop takes O(n) time. So the total time is O(n^2).

If we store nodes not yet included in tree as a red-black tree then algorithm takes O(log n) time.

Disadvantages of Prim’s algorithm:

  1. List of edges has to be searched from beginning as new edge gets added.

  2. If there are more than one edges having same weight then all possible spanning trees are required to be found for final minimal tree.