2.5.2. Kruskal's Algorithm

Try these first

1. 1.

   Define a spanning tree.

   Hint

   Think about 'spanning' all vertices.

2. 2.

   What does Kruskal's Algorithm help us find?

   Hint

   Focus on minimizing costs!

3. 3.

   What does Kruskal's Algorithm primarily aim to find?

   • A shortest path
   • A minimum spanning tree
   • A Hamiltonian cycle

   Hint

   Think about what trees do!

4. 4.

   True or False: Kruskal's Algorithm can create cycles when adding edges.

   • True
   • False

   Hint

   Focus on what it means to maintain a tree structure.

5. 5.

   Given a modified graph with weights, calculate the minimum spanning tree using Kruskal's Algorithm and state the final weight.

   Hint

   Remember to sort first and revisit all edges methodically.

6. 6.

   Analyze the effectiveness of Kruskal's Algorithm in large dense graphs versus sparse graphs. Discuss the implications on performance.

   Hint

   Consider edge counts relative to vertices when evaluating performance.