DESIGN AND ANALYSIS OF ALGORITHMS
PRIM’S ALGORITHM
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components. The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.
Here, we begin with some vertex v in a given graph G= (V, E) and grows until the tree spans all the vertices in V. Each step adds to the tree a light edge that connects the tree to an isolated vertex – one to which no edge of the tree is incident.
In the algorithm, the connected graph G, edge weight w and the root r of the minimum spanning tree to be grown are inputs to the algorithm. During execution of the algorithm, all vertices that are not in the tree reside in a min-priority queue Q based on the minimum weights. The attribute v. names the predecessor of v in the tree.
PRIM’S ALGORITHM (G, w, r)
1. for each u G.V-{r}
2. do u. key
3. u. = NIL
4. r. key=0
5. r.
6. Q=G.V
6. While Q ≠
7. do u= EXTRACT-MIN(Q)
8. for each v G.Adj[u]
9. do if v Q and w (u, v) < v. key
10. then v. u
11. v. key= w (u, v)
ANALYSIS
Lines 1-5 comprise of initialization of vertices in the graph which takes O (V) time. The queue Q in line 6 can be implemented using a BUILD-MIN-HEAP procedure in O (V) time. The body of the while loop is executed |V| times, and since each EXTRACT-MIN operation takes O(log V) time, the total time for all calls to EXTRACT-MIN is O(V log V). The for loop in lines 8-11 is executed O (E) times altogether, since the sum of the lengths of all adjacency lists is 2 |E|. The assignment in line 11 involves an implicit BUILD-MINHEAP, which can be implemented in O (log V) time. Thus, the total time for Prim's algorithm is O (V log V + E log V) = O (E log V).
The asymptotic running time of Prim’s algorithm can be improved by using Fibonacci heaps. If we use a Fibonacci heap to implement the min-priority queue Q, the running time can be brought down to O (E + V logV).
Similar Threads:
- The heapsort algorithm in Design and analysis of algorithms free notes
- Randomized algorithms in Design and analysis of algorithms free pdf
- Analyzing divide-and-conquer algorithms in Design and analysis of algorithms free pdf
- Efficiency of algorithm in Design and analysis of algorithms free notes
- Introduction to Algorithms Design and analysis of algorithms free pdf