Lecture Notes for CS 512, Algorithm Design

Minimum Spanning Trees - 26 January 2000

1. spanning trees

   1. both bfs and dfs produce spanning trees

   2. unconnected or directed graphs are problematic

2. minimum weight spanning trees over weighted graphs

3. the generic minimum spanning tree (mst) algorithm - cuts and greed

   1. cuts - a form of divide and conquer

      1. the mst unifies vertices into a connected tree

      2. a cut partitions vertices into disconnected parts

      3. any respecting cut indicates places where more work is needed

      4. cuts are an important concept in graph algorithms (flow problems)

   2. greed - which edge across a respecting cut to choose?

      1. is the minimum edge across a respecting cut an acceptable choice?

4. kruskal's mst algorithm - bottom up

   1. define the cut to include the lowest weight edge not yet in the mst

   2. if the cut is safe, add the edge to the mst

   3. if no such cut is safe, discard the edge

5. prim's mst algorithm - top down

   1. define the cut to be the frontier of the mst

This page last modified on 31 January 2000.