Prims algorithm, Data Structure & Algorithms

Assignment Help:

Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up disjoint sets.

It employs two disjoint sets A and A. Prim's algorithm works by iterating through the nodes and then determining the shortest edge from the set A to that of set A (that means outside A), followed by the adding up the node to the new graph. While all the nodes are processed, we have a minimum cost spanning tree.

Instead building a sub-graph by inserting one edge at a time, Prim's algorithm builds tree one vertex at a time.

The steps in Prim's algorithm are as:

Consider G be the graph having n vertices for which minimum cost spanning tree is to be made.

Consider T be the minimum spanning tree.

consider T be a single vertex x.

while (T has fewer than n vertices)

{

find the smallest edge connecting T through G-T

add it to T

}

Let the graph of Figure.  And another Figure shows the various steps involved in the construction of Minimum Cost Spanning Tree of graph of this Figure

2433_Prims Algorithm.png

Figure: Construction of Minimum Cost Spanning Tree for the Graph of Figure by application of Prim's algorithm

The following are several steps in the construction of MST for the graph of Figure via Prim's algorithm.

Step 1:  We start along a single vertex (node). Now the set A has this single node and set A has rest of the nodes. Add the edge along the lowest cost from A to A. The edge along cost 4 is added.

Step 2: Lowest cost path through shaded portion of the graph to the rest of the graph (edge along cost 3) is chosen and added to MST.

Step 3: Lowest cost path through shaded portion of the graph to the rest of the graph (edge with cost 6) is chosen and inserted to MST.

Step 4: Lowest cost path from shaded portion of graph to the rest of the graph (edge along cost 73) is chosen and added to MST.

Step 5: The next lowest cost edge to the set not in MST is 8 but makes a cycle. So, it is discarded. The next lowest cost edge 9 is inserted. Now the MST has all the vertices of the graph. This results in the MST of the original graph.

Comparison of Kruskal's algorithm & Prim's algorithm

 

Kruskal's algorithm

Prim's algorithm

Principle

Based on generic minimum cost

spanning tree algorithms

A special case of generic minimum

cost spanning tree algorithm. Operates like Dijkstra's algorithm for finding shortest path in a graph.

Operation

Operates on a single set of

edges in the graph

Operates on two disjoint sets of

edges in the graph

Running time

O(E log E) where E is the

number of edges in the graph

O(E log V), which is

asymptotically same as Kruskal's algorithm

From the above comparison, it might be observed that for dense graphs with more number of edges for a given number of vertices, Prim's algorithm is more efficient.


Related Discussions:- Prims algorithm

Algorithm for binary search, Q. Write down the algorithm for binary search....

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Binary trees, A binary tree is a special tree where each non-leaf node can ...

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Hashing and hash functions, Q. Describe the term hashing. Explain any two u...

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.

Explain about the doubly linked list with neat diagram, Problem 1. Expl...

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

Explain the scan-line algorithm, Explain the Scan-Line Algorithm This i...

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

Deletion of a node from an avl tree, For AVL trees the deletion algorithm i...

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

Recurrence relation, solve the following relation by recursive method: T(n...

solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

Interest, I=PR/12 numbers of years : Interest Rate up to 1 years : 5...

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

If-then-else statements, In this example, suppose the statements are simple...

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd