Union-find (DSU): merging disjoint sets · 2 of 2
Minimum spanning trees
Connect every vertex for the lowest total weight with Kruskal’s algorithm and union-find, see why each lightest edge is safe to take, and use Prim’s algorithm when the graph is dense.
Books1
Links2
- Algorithms, Chapter 7: Minimum spanning trees Section 7.2 proves by an exchange that the lightest edge leaving any set of vertices belongs to the minimum spanning tree, and sections 7.4 and 7.5 build Prim’s and Kruskal’s algorithms on that fact. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Minimum Spanning Trees Kruskal’s algorithm with this DSU and Prim’s algorithm with a heap, both solving CSES Road Reparation, where a graph that is not connected has to be reported, followed by problems. usaco.guide (opens in a new tab)