www.reallygreatsite.
com
THE PRIM’S
ALGORITHM
Minimum spanning tree
Presented by- Jayesh Prakash narayan
Roll number- 28
ADT24SOCB0510
SY-20
What is MST?
A Minimum Spanning Tree (MST) is a subgraph of a
connected, undirected graph that connects all the
vertices together, without any cycles, and with the
minimum possible total edge weight. It's like finding the
most efficient way to connect all points.
In a given weighted graph, there can be many spanning
trees, but only one (or sometimes a few with the same
minimum weight) minimum spanning tree. Its unique
properties make it fundamental in computer science.
Prim’s algorithm: Core principal
Prim’s Algorithm builds the Minimum Spanning Tree (MST) step by step.
It starts with any one vertex and grows the MST by adding the smallest edge that connects
a new vertex to the already formed tree.
At each step, it chooses the minimum weight edge that links the tree to a vertex not yet
included.
This process repeats until all vertices are included in the MST.
Initial State (Start A)
⟶ Priority Queue (PQ) = {(A-B:2), (A-C:3)}
Simulation of Prim’s Algorithm:
⟶ Visited = {A}
Step 1: Select A-B (Weight 2)
⟶ Add edge (A-B) to MST
⟶Visited = {A, B}
MST Weight = 2
Step 2: Select A-C (Weight 3)
⟶Add edge (A-C) to MST
→
⟶Insert edges from C {(C-D:1), (C-E:7), (C-B:5)}
⟶Visited = {A, B, C}
MST Weight = 5
Step 3: Select C-D (Weight 1)
⟶Add edge (C-D) to MST
⟶Insert edge (D-E:4)
⟶Visited = {A, B, C, D}
⟶MST Weight = 6
Step 4: Select D-E (Weight 4)
⟶Add edge (D-E) to MST
⟶Visited = {A, B, C, D, E}
⟶MST Weight = 10
Start:
Visited = {A}
-->Pseudocode of Prim’s Algorithm
MST_Weight = 0
PQ = {(A-B:2), (A-C:3)}
Step 1: Select A-B (Weight 2)
Add edge (A-B) to MST
Visited = {A, B}
MST_Weight = 2
Step 2: Select A-C (Weight 3)
Add edge (A-C) to MST
→
Insert edges from C {(C-D:1), (C-E:7), (C-B:5)}
Visited = {A, B, C}
MST_Weight = 5
Step 3: Select C-D (Weight 1)
Add edge (C-D) to MST
Insert edge (D-E:4)
Visited = {A, B, C, D}
MST_Weight = 6
Step 4: Select D-E (Weight 4)
Add edge (D-E) to MST
Visited = {A, B, C, D, E}
MST_Weight = 10
End:
MST complete
Java code for
Prims algorithm
Real life use case of MST:
Network Design
Designing computer, telecommunication, or electrical networks with the minimum
cable/wire cost.
Example: Laying internet cables to cities at minimum cost.
Transportation & Roads
Building roads/railways between cities such that the total construction cost is minimum.
Electrical Grid Connections
Power companies use MST for connecting power stations and cities with minimum wiring.
Cluster Analysis (Data Science/AI)
MST helps in grouping similar data points efficiently.
Water Pipeline or Gas Line Distribution
Finding the least expensive way to lay pipelines covering all required locations.
Applications:
Key Applications of Prim’s Algorithm (MST):
Network Design
Used in building LAN/WAN and telecommunication systems.
Ensures that all nodes (computers, servers, routers) are connected with the least cable cost.
Prevents redundant wiring while maintaining full connectivity.
Circuit Optimization
Helps in electrical circuit design and VLSI chip layout.
Reduces the length of wires while still connecting all required components.
Saves material, reduces power loss, and improves overall efficiency.
Transportation Networks
MST helps in designing cost-effective road, railway, or pipeline routes.
Ensures all cities or stations are connected using the minimum construction resources.
Widely applied in logistics, supply chains, and metro planning.
Clustering in Machine Learning
MST-based clustering is used in pattern recognition and data mining.
Helps in grouping data points into clusters by identifying hidden relationships.
Useful in image segmentation, anomaly detection, and social network analysis.
AI Usage:
Transparency in Creation Process:
Tools Used:
→
ChatGPT refined pseudocode & explanations
→
Gamma AI slide design generation
→
Bolt step-by-step simulation snapshots
Prompts Used:
ChatGPT: “Polish pseudocode and explanations for Prim’s Algorithm”
Bolt: “Generate step-by-step snapshots for Prim’s Algorithm on a 5-node graph”
Outputs Generated:
→
ChatGPT text + pseudocode
→
Gamma AI slides & layout
→
Bolt simulation images
Note: All AI-generated content was reviewed, verified, and finalized by the student.
THANK
YOU!
