Held: Monday, 2 November 2015

Back to Outline 25 - Implementing the Graph ADT. On to Outline 27 - Minimum Spanning Trees, Continued.

Summary

We consider minimum spanning trees (MSTs) and techniques for buiding MSTs.

Related Pages

Overview

• Minimum spanning trees.
• Two algorithms: Prim's algorithm and Kruskal's algorithm.
• Examples.
• Proofs of correctness.

Administrivia

• 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

• 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

Minimum Spanning Trees

• Minimum spanning tree: Given a connected weighted graph, G(E,V), pick a subset of the edges, E', such that (a) G(E',V) is connected and (b) for any other subset of edges, F, weightsum(F) >= weightsum(E).
• What algorithmic approaches do we have?
  • Find similar algorithms
  • Divide and conquer
  • Greed
• Which is most likely to be useful?

Prim's Algorithm

• A greedy algorithm.
• Divide the vertices in the graph into those in the MST and those not in the MST.
• Repeatedly add the shortest edge from MST to non-MST.

• Practice (stolen from Walker):

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

• Why is Prim's algorithm correct?

  • What proof techniques do you know?
• How efficient is Prim's algorithm in the abstract?
• What assumptions have we made about the underlying operations?
• Can we choose particular implementations to make it more efficient (assume we can use vertices as indicies into tables)?

Kruskal's Algorithm

• Another greedy algorithm.
• Identify each connected component (initially n different ones, because we have no edges)
• Repeatedly the smallest edge remaining that connects to separate components.

• Practice (stolen from Walker):

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

• Why is Kruskal's algorithm correct?

• How efficient is Kruskal's algorithm in the abstract?
• What assumptions have we made?
• Can we use particular data structures to make it more efficient?