Implement Kruskal's and Prim's MST

greedy edge and vertex growth

Challenge 4 of GraphsAdvanced~60 minFree

Design least-cost networks by building a Minimum Spanning Tree. You will implement a Union-Find (disjoint set) structure, then Kruskal's and Prim's algorithms, and finally use the MST to test whether a graph is connected. Graphs are undirected with integer nodes 0..n-1 and edges given as (u, v, weight).

5 steps

  1. 1Union-Find (Disjoint Set)
  2. 2Kruskal's MST Weight
  3. 3Kruskal's Chosen Edges
  4. 4Prim's MST Weight
  5. 5Connectivity via the MST
Start step 1