codaBack to Academy
graphs
Kruskal's MST
Kruskal's algorithm finds a minimum spanning tree by sorting all edges by weight and greedily adding the smallest edge that does not form a cycle. It uses the Union-Find (disjoint set) data structure for efficient cycle detection. It works well on sparse graphs.
Use Cases
- •Network design (minimum cost to connect all nodes)
- •Clustering by removing the most expensive MST edges
- •Laying cable or pipeline with minimum total cost
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(E log E) | O(E log E) | O(E log E) |
| Space | O(V + E) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...