CSC301.01 2015F, Class 26: Minimum Spanning Trees
=================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Minimum spanning trees.
* Two algorithms: Prim's algorithm and Kruskal's algorithm.
* Examples.
* Proofs of correctness.
* Efficiency.

Preliminaries
-------------

### Admin

* Question for student athletes (and other students): 
  Should we allow practice to continue beyond the end of the season?

Checking in on terms and algorithms.  I am confident in my understanding;
I know some things; I don't know.

* Minimum spanning tree (MST).
* Any algorithm to construct a MST.
* Prim's algorithm for MSTs.
* Kruskal's algorithm for MSTs.
* Union-find.

### Upcoming Work

* HW (Due Wednesday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28

### Extra Credit

#### Academic

* CS Table Tuesday: Why is everyone so mean on the Internet?
* CS Extras Thursday: Walker on the fun of Bluetooth
* Sexual Misconduct at Grinnell College: Results from the 2013 and 2015
  Sexual Conduct Surveys.  1-3 pm, November 8, JRC 101.

#### Peer Support

  
### Questions

_There is no topological sort for 5-2.  What should we do?_

> Indicate why there is no way to topologically sort 5-2.

> Remove an edge to permit topological sort and then topologically sort it.

> Ask yourself whether this was intentional on Skiena's part or not (no
  answer to this last part needed).

Minimum spanning trees
----------------------

Given a weighted non-directed connected graph, G(V,E) [connected: path
from any vertex to any other vertex] [complete: edge from every vertex
to every other vertex], build a new connected graph G(V,E'), s.t.

* E' is a subset of E.
* If G(V,F) is connected and F is a subset of E, the sum of the weights
  in F is less than or equal to the sum of the weights in E'.

Why do we call it a minimum spanning tree and not a minimum spanning graph?

* If there any cycles, throw away one of the edges, and it's still a spanning
  graph.  Take away enough, it's a tree.

What techniques can we use?

* Broad algorithmic strategies
    * Divide and conquer
    * Greed
    * Exhaustive search
* Tools
    * Recursion
* Processes
    * Think a lot
    * Look for similar problems

Here's a graph!  (Picture on the board.)

     Vertices: A, B, C, D, E, F, G
     Edges: AB(6), AC(7), AE(8), BD(9), CD(1), CE(1), CF(2), DF(5),
     EF(10), EG(14), FG(8).

An Exhaustive Algorithm
-----------------------

* Find each subset, E' of E.
* Determine whether G(V,E') is a minimum spanning tree.
* Find the smallest such E'.

Three Approaches
----------------

* Start with all the edges, repeatedly throw away large edges if you can do so.
* Start with no edges, repeatedly add the smallest edge that doesn't cause
  a cycle.
* Start with no edges and one node, repeatedly "grow" the tree in the
  cheapest way possible.