Stanford CS161 Lecture 15: Proving Prim and Kruskal with the Cut Property
The heart of MST algorithms is an invariant: the selected edges remain contained in some MST. The cut property proves that every step of Prim and Kruskal is safe.
The heart of MST algorithms is an invariant: the selected edges remain contained in some MST. The cut property proves that every step of Prim and Kruskal is safe.