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.