Ask
Login
1
15kviews
Compare Prims and Kruskals method for finding Minimum spanning Tree find MST for following using prims method.
written 7.8 years ago by gravatar for teamques10 teamques10 ★ 68k •   modified 4.6 years ago
analysis of algorithms
ADD COMMENT EDIT
1 Answer
3
82views
written 7.8 years ago by gravatar for teamques10 teamques10 ★ 68k

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 COMMENT EDIT
Please log in to add an answer.