Prim's Algorithm (7 Marks – RGPV)
Prim's Algorithm
Definition
Prim's Algorithm is a Greedy Algorithm used to find the Minimum Spanning Tree (MST) of a connected,
weighted, undirected graph. It starts from any vertex and repeatedly selects the minimum weight edge
that connects a new vertex to the growing tree without forming a cycle.
Simple Definition (Easy to Remember):
Prim's Algorithm is a Greedy Algorithm that constructs a Minimum Spanning Tree by repeatedly
selecting the minimum weight edge connected to the growing tree.
Characteristics of Prim's Algorithm
1. Greedy Approach
2. Chooses the minimum-weight edge at every step.
3. Builds Tree Gradually
4. Starts from one vertex and grows the tree by adding one vertex at a time.
5. No Cycle Formation
6. The selected edge should never create a cycle.
7. Connected Graph
8. Works only on connected, weighted, undirected graphs.
9. Minimum Cost
10. Produces a Minimum Spanning Tree having the minimum total edge weight.
11. Contains (V − 1) Edges
12. For V vertices, the MST contains exactly V − 1 edges.
1
Greedy Choice Property
The Greedy Choice Property states that at every step, Prim's Algorithm selects the smallest weight edge
that connects a vertex already present in the tree to a vertex outside the tree.
This local optimal choice at every step results in the Minimum Spanning Tree.
Example
Consider the graph:
A -----2----- B
| \ |
6 3 5
| \ |
C -----4----- D
If we start from A, the algorithm selects:
• A → B (2)
• A → C (3)
• C → D (4)
Total Cost = 2 + 3 + 4 = 9
Optimal Substructure
Prim's Algorithm satisfies the Optimal Substructure Property because after adding the minimum-cost
edge, the remaining graph becomes a smaller Minimum Spanning Tree problem. Solving this smaller
problem optimally leads to the optimal solution for the original graph.
Algorithm
Step 1: Select any vertex as the starting vertex.
Step 2: Mark it as visited.
Step 3: Find the minimum-weight edge connected to the visited vertices.
Step 4: Select the edge if it does not form a cycle.
Step 5: Add the new vertex to the tree.
Step 6: Repeat Steps 3–5 until all vertices are included.
Step 7: The selected edges form the Minimum Spanning Tree.
2
Example
Consider the following graph:
Edge Weight
A–B 2
A–C 3
A–D 6
B–D 5
C–D 4
Step 1
Start from A
Visited = {A}
Step 2
Choose the smallest edge connected to A.
A→B=2
Visited = {A, B}
Step 3
Available edges:
•A→C=3
•B→D=5
•A→D=6
Choose
A→C=3
Visited = {A, B, C}
3
Step 4
Available edges:
•C→D=4
•B→D=5
•A→D=6
Choose
C→D=4
Visited = {A, B, C, D}
Minimum Spanning Tree
Selected Edge Weight
A–B 2
A–C 3
C–D 4
Total Cost = 2 + 3 + 4 = 9
Time Complexity
• Using Adjacency Matrix: O(V²)
• Using Min Heap (Priority Queue): O(E log V)
Space Complexity
• O(V + E)
Advantages
1. Simple and easy to understand.
2. Produces the Minimum Spanning Tree.
3. Efficient for dense graphs.
4. Guarantees minimum total cost.
5. Widely used in network design.
4
Disadvantages
1. Works only for connected graphs.
2. Cannot be directly applied to directed graphs.
3. Large graphs may require more memory.
4. Performance depends on the graph representation.
5. Not suitable for disconnected graphs.
Applications
Prim's Algorithm is used in:
• Computer Network Design
• Telephone Networks
• Electrical Power Distribution
• Road Construction
• Railway Network Planning
• Water Supply Systems
• Cable TV Networks
• LAN Design
• Pipeline Networks
• Network Optimization Problems
Why is Prim's Algorithm a Greedy Algorithm?
Prim's Algorithm always chooses the minimum-weight edge that connects the growing tree to a new
vertex. Since it makes the best local choice at every step, it follows the Greedy Strategy and finally
produces the Minimum Spanning Tree.
Conclusion
Prim's Algorithm is one of the most important Greedy Algorithms for finding the Minimum Spanning
Tree. It builds the tree step by step by selecting the minimum-cost edge without creating a cycle. Due to its
efficiency and simplicity, it is widely used in communication, transportation, and network design.
⭐ Keywords for Revision
• Prim's Algorithm
• Greedy Algorithm
• Minimum Spanning Tree (MST)
• Connected Graph
5
• Weighted Graph
• Undirected Graph
• Minimum Edge
• No Cycle
• V − 1 Edges
• Priority Queue
• Min Heap
• O(V²)
• O(E log V)
• Network Design