Minimum spanning tree: Prim and Kruskal

Minimum spanning tree: Prim and Kruskal

Key points

• A minimum spanning tree connects all vertices with least total edge weight.
• Kruskal sorts edges and adds each one that does not form a cycle, using DSU.
• Prim grows the tree from one vertex using a priority queue.