Minimum Spanning Tree

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

  • In the context of Graph Theory, define Cycle, Acyclic Graph, and Tree.
  • Describe what spanning tree is and why constructing minimum spanning trees are useful.
  • Trace Prim's algorithm for finding a minimum spanning tree.
  • Trace Kruskal's algorithm for finding a minimum spanning tree.
  • Explain how to implement Prim's algorithm, comparing various approaches to finding the next min edge, and the resulting time/space tradeoffs between them.
  • Explain how to implement Kruskal's algorithm, comparing various approaches to checking for cycles, and the resulting time/space tradeoffs between them.