Question: Compare Prims and Kruskals method for finding Minimum spanning Tree find MST for following using prims method.
2

Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10M

Year: Dec 2016

ADD COMMENTlink
 modified 2.5 years ago  • written 2.5 years ago by Barkha • 750
2 Ans:

Prims Kruskal’s
This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices. This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices.
Prim’s algorithm initializes with a node Kruskal’s algorithm initiates with an edge
Prim’s algorithms span from one node to another Kruskal’s algorithm select the edges in a way that the position of the edge is not based on the last step
In prim’s algorithm, graph must be a connected graph Kruskal’s can function on disconnected graphs too.
Prim’s algorithm has a time complexity of O(V2) Kruskal’s time complexity is O(logV).

Problem:

Step1:

We will first select a minimum distance edge from given graph. V={b,d} Cost=1

Step 2:

The next minimum distance edge is d-c. This edge is adjacent to previously selected vertex d. V={b,d,c} Cost=3

Step 3:

The next minimum distance edge is a-b. This edge is adjacent to previously selected vertex b. V={b,d,c,a} Cost=5

Step 4:

The next minimum distance edge is d-f. This edge is adjacent to previously selected vertex d. V={ b,d,c,a ,f} Cost=8

Step 5:

The next minimum distance edge is f-g. This edge is adjacent to previously selected vertex f. V={ b,d,c,a ,f ,g} Cost=10

Step 6:

The next minimum distance edge is g-h. This edge is adjacent to previously selected vertex g. V={ b,d,c,a ,f ,g ,h} Cost=11

Step 7:

The next minimum distance edge is e-h. This edge is adjacent to previously selected vertex h. V={ b,d,c,a ,f ,g ,h} Cost=15

Hence, the above is the minimum spanning tree with total cost 15.

ADD COMMENTlink
 written 2.5 years ago by Barkha • 750
Please log in to add an answer.