ADMIN: I'm still preparing hw4, nothing is due now,
but you should be reading at least 4.3.

Continuing from last time: greedy algorithms for the MST.

In the slides, this means continuing around page 18.

The cut property:
    The min weight edge across a cut is in the MST.
    (For ties: every min weight edge is in some MST.)

The greedy algorithm:
    Initially the MST is an empty set of edges, T.  While
    there is some cut which is not crossed by T, add a
    min weight edge across this cut to T.

Claim: If G is connected, this algorithm finds a MST!
   (If G is not connected, it can find a min weight forest
    of trees, each tree spanning each component of G.)

See: 43DemoGreedy.pdf

This deserves a proof, since "greed" is often not optimal
for other problems (like greedy TSP heuristics).

Two efficient implementaiton ideas:
    Kruskal (try edges in sorted order, guided by UF)
    see: 43DemoKruskal.pdf
    Prim (grow one tree with boundary edges in minheap, two variants)
    see: 43DemoPrim.pdf

These algorithms are fast, taking time about O(E log V).

Before getting into the details (code) of Kruskal and Prim,
I also want to mention the Geometric case:

Suppose your V vertices are points in the plane, and every pair has an
implicit edge whose length is their Euclidean distance.  Then how
quickly can you compute their MST?  It turns out that the main
challenge here is to avoid computing all O(V*V) possible edges.

One approach, OK in practice but no help in the worst case, is to just
build a graph with all edges of length up to some threshold delta.  I
have some example code that tries to do this in geom/:

   cd geom
   make

There is in fact a much faster solution: compute the Delaunay
triangulation (a planar graph of O(V) edges that must include the MST
edges).  There is a O(V log V) algorithm for this, e.g. Fortune's
algorithm, which is animated here:
  http://www.diku.dk/hjemmesider/studerende/duff/Fortune/