Objective of prim’s algorithm is to understand the Greedy method to obtain a minimum cost spanning tree edge by edge.
Greedy method :
- 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.
- Any subset that satisfies these constraints is called a feasible solution.
- We find a feasible solution that either maximizes or minimizes a given objective function.
- A feasible solution that does this is called an ‘Optimal Solution’ .
Greedy algorithm :
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;
}
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.
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.)
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 ].
- mincost =0;
- For (i=2 to n) do near[ i ]=1;
- Near[1]=0 //vertex 1 is initially in ‘t’ .
- For(i=1 to n-1) do
- { // find n-1 edges of tree.
- Let j be an index such that
- Near[ j ] !=0 & cost[ j ][ near[ j ] ] is minimum.
- // computation of j requires linear loop
- // not shown above.
- t[ i ][1] = j; t[ i ][2]= near[ j ];
- mincost=mincost + cost[ j ][near [ j ] ];
- Near[ j ] =0;
- For( k= 1 to n ) do //update near[ ]
- If(near[ k ] !=0) && (cost[ k ][ near[ k ] ] > cost[ k ][ j ])
- Near[ k ]=j;
- }
- return mincost.
|
Stages in Prim’s algorithm :
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:
- List of edges has to be searched from beginning as new edge gets added.
- If there are more than one edges having same weight then all possible spanning trees are required to be found for final minimal tree.
Leave a Reply