Greedy Algorithms: Kruskal’s Algorithm

• Read section 9.2 (pages 325-333)
• How does Kruskal’s algorithm grow the minimum spanning tree? How does that differ from Prim’s?
  • Would Kruskal’s be classified as a greedy algorithm? why?
  • What does the ecounter variable do?
  • What are the difficult parts of Kruskal’s algorithm?
  • Does the start vertex for the algorithm affect the order in which edges are chosen?
• What is the union-find structure? What operations does it allow?
  • What are the operations that Kruskal’s algorithm needs from such a structure?
  • Show how the structure can be used in the context of Kruskal’s algorithm.
  • What are the two main alternatives of the union-find structure?
• Practice problems: 9.2.1, 9.2.2, 9.2.12