Minimum Spanning Tree
From Rice Wiki
A minimum spanning tree is
- a tree, meaning it has no cycle
- minimum, meaning it has minimum weight
- spanning, meaning it connects all nodes
MST Problem
The MST problem takes a connected graph and outputs an MST for that graph.
Approach: Greedy
The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of vs.
Given the MST of , the MST of should be that of plus the edge that connects to that is the shortest.