Given. Undirected graph G with positive edge weights (connected).
Def. A spanning tree of G is a subgraph T that is both a tree (connected and acyclic) and spanning (includes all of the vertices).
Goal. Find a min weight spanning tree.
- Start with all edges colored gray.
- Find cut with no black crossing edges; color its min-weight edge black.
- Repeat until V - 1 edges are colored black.
Edge abstraction needed for weighted edges.
Maintain vertex-indexed array of Edge lists.
Q. How to represent the MST?
Consider edges in ascending order of weight.
- Add next edge to tree T unless doing so would create a cycle.
- Start with vertex 0 and greedily grow tree T.
- Add to T the min weight edge with exactly one endpoint in T.
- Repeat until V - 1 edges.