'water' Analysis by Spencer Liang/Richard Peng

Consider a graph with V vertices and E edges. We can compute its minimum spanning tree in O(E log V) time with Prim's algorithm.

The algorithm basically starts with the tree as any single vertex, then repeatedly add the mostly 'connected' vertex to the tree. This 'connectedness' is measured by the shortest edge between that vertex and a vertex already included in the tree. This can be implemented in O(V^2) time by storing the graph in an adjacency matrix, then update the connectedness of vertices as a new vertex is added to the tree. The correctness of the above algorithm is fairly intuitive, but somewhat tricky to prove. The basic idea is that adding any edge to a tree gives a cycle, from which the most costly edge can be removed. So if the current edge is not one of lowest cost, it can be substituted to give spanning tree that's no more expensive.

Imagine a water reservoir at pasture 0, and let the cost of building a pipe from the reservoir to pasture k be W_k. Then digging a well in pasture k is equivalent to building a pipe from pasture 0 to pasture k. The pastures from 0 to k and the possible pipes between them form a graph, and the desired answer is the weight of its minimum spanning tree.