Introduction

Prim's Algorithm is one of the most important algorithms used to find a Minimum Spanning Tree (MST).

You are given:

  • A weighted undirected graph
  • n vertices
  • Weighted edges

Goal:

Connect all vertices with minimum total cost.

Example

Input

0 -- 1 (2)
|    /
|  /
 2
 |
 3

Edges:
0-1 = 2
0-3 = 6
1-2 = 3
1-3 = 8
2-3 = 7

Output

MST Cost = 11

Key Observation

Instead of sorting all edges, Prim's grows the MST one node at a time by always choosing the minimum weight edge.

Algorithm

  1. Start from any node.
  2. Add all neighboring edges into a min heap.
  3. Pick minimum weight edge.
  4. If node is already visited, skip it.
  5. Otherwise include it in MST.
  6. Add its neighbors into heap.
  7. Continue until all nodes are visited.

Dry Run

Start From Node 0

Cost = 0
Visited = {0}

Pick Edge (0,1)

Cost = 2
Visited = {0,1}

Pick Edge (1,2)

Cost = 2
Visited = {0,1}

Pick Edge (0,3)

Cost = 11
Visited = {0,1,2,3}

Answer:

11

Approach : Greedy + Min Heap

Prim's Algorithm starts from one node and keeps expanding the tree using the smallest available edge.

A Priority Queue helps efficiently select the minimum weight edge.

Practice


Complexity Analysis

Time Complexity: O(E log V)Explanation: Each edge may be inserted into the priority queue and heap operations take O(log V) time.

Space Complexity: O(V + E)
Explanation: The adjacency list stores all edges and the priority queue stores candidate edges during execution.

Why This Problem is Important

Prim's Algorithm is one of the two major Minimum Spanning Tree algorithms and is frequently asked in coding interviews.

Common Beginner Mistakes

  • Using a normal queue instead of a min heap.
  • Forgetting visited checks.
  • Adding duplicate nodes into MST.
  • Confusing MST with shortest path algorithms.

Interview Tip

Always mention:

Prim's Algorithm grows the MST one node at a time by repeatedly selecting the minimum weight edge connecting the tree to an unvisited node.

Related Questions

  • Kruskal Algorithm
  • Min Cost to Connect All Points
  • Network Delay Time
  • Dijkstra Algorithm
  • Graph Valid Tree

Final Takeaway

Prim's Algorithm is a Greedy MST algorithm that uses a Priority Queue to efficiently build a Minimum Spanning Tree with minimum total weight. It is one of the most important graph algorithms for interviews and competitive programming.