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.2 years ago  • written 2.2 years ago by gravatar for Barkha Barkha750
2

enter image description here

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.

enter image description here

V={b,d} Cost=1

Step 2:

The next minimum distance edge is d-c. This edge is adjacent to previously selected vertex d.

enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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.2 years ago by gravatar for Barkha Barkha750
Please log in to add an answer.