**Prim’s Algorithm-**

- Like
**Kruskal’s Algorithm**, Prim’s Algorithm is another greedy algorithm used for finding the Minimum Spanning Tree (MST) of a given graph. - The graph must be weighted, connected and undirected.

**Steps for implementing Prim’s Algorithm-**

**Step-01:**

- Randomly choose any vertex.
- We usually select and start with a vertex that connects to the edge having least weight.

**Step-02:**

- Find all the edges that connect the tree to new vertices, then find the least weight edge among those edges and include it in the existing tree.
- If including that edge creates a cycle, then reject that edge and look for the next least weight edge.

**Step-03:**

- Keep repeating step-02 until all the vertices are included and Minimum Spanning Tree (MST) is obtained.

**Time Complexity-**

Worst case time complexity of Prim’s Algorithm

= O(ElogV) using binary heap

= O(E + VlogV) using Fibonacci heap

**Explanation-**

- If adjacency list is used to represent the graph, then using breadth first search, all the vertices can be traversed in O(V + E) time.
- We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included in the MST.
- To get the minimum weight edge, we use min heap as a priority queue.
- Min heap operations like extracting minimum element and decreasing key value takes O(logV) time.

So, overall time complexity

= O(E + V) x O(logV)

= O((E + V)logV)

= O(ElogV)

This time complexity can be improved and reduced to O(E + VlogV) using Fibonacci heap.

**PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM-**

**Problem-01:**

Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-

**Solution-**

For a video solution explaining the solution step by step, **watch this video**.

**Step-01:**

**Step-02:**

**Step-03:**

**Step-04:**

**Step-05:**

**Step-06:**

Since all the vertices have been included in the MST, so we stop.

Weight of the MST

= Sum of all edge weights

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

**Problem-02:**

Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-

**Solution-**

For a video solution explaining the solution step by step, **watch this video**.

The Minimum Spanning Tree (MST) obtained by the application of Prim’s Algorithm on given graph is-

Weight of the MST

= Sum of all edge weights

= 1 + 4 + 2 + 6 + 3 + 10

= 26 units

To gain better understanding of the concepts of Prim’s Algorithm and to solve more problems,

To practice previous years GATE problems based on Prim’s Algorithm,

**Download the ****handwritten notes of “Prim’s Algorithm” here-**

Get more notes and other study material of **Design and Analysis of Algorithms (DAA)**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.