DESIGN AND ANALYSIS OF ALGORITHMS

PRIM’S ALGORITHM

Prim's algorithmis 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 takesO(V) time. The queue Q in line 6 can be implemented using a BUILD-MIN-HEAP procedure inO(V) time. The body of thewhileloop is executed |V| times, and since each EXTRACT-MIN operation takesO(logV) time, the total time for all calls to EXTRACT-MIN isO(VlogV). Theforloop in lines 8-11 is executedO(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 inO(logV) time. Thus, the total time for Prim's algorithm isO(VlogV+ElogV) = O (ElogV).

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