codaBack to Academy
graphs
Prim's MST
Prim's algorithm grows a minimum spanning tree from a starting vertex by always adding the cheapest edge that connects a vertex in the tree to a vertex outside it. It uses a priority queue for efficiency. It performs well on dense graphs with many edges.
Use Cases
- •Network design on dense graphs
- •Approximation algorithms for NP-hard problems (e.g., TSP)
- •Image segmentation in computer vision
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O((V + E) log V) | O((V + E) log V) | O((V + E) log V) |
| Space | O(V + E) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...