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 a spanning tree is and why constructing minimum spanning trees is 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.

This chapter does not have a starter/solution code.