5.2.3. Greedy Algorithm Comparison

Try these first

1. 1.

   What does Kruskal's algorithm aim to find?

   Hint

   Think about the structure of trees and costs.

2. 2.

   What is the purpose of sorting edges in Kruskal's algorithm?

   Hint

   Consider why choosing smaller edges might be beneficial.

3. 3.

   What does Kruskal's algorithm prioritize when selecting edges?

   • Random edges
   • Largest edges first
   • Smallest edges first

   Hint

   Consider what a greedy algorithm would typically choose.

4. 4.

   True or False: In Kruskal's algorithm, it's possible to create cycles when adding edges.

   • True
   • False

   Hint

   Think about the cycle prevention mechanism.

5. 5.

   Given a graph with vertices A, B, C, D, E and the following edges: {(A, B, 3), (B, C, 1), (C, D, 4), (A, D, 2), (B, D, 5), (D, E, 2)}. Apply Kruskal's algorithm to find the minimum spanning tree.

   Hint

   Draw the edges and keep track of added edges to visualize cycles.

6. 6.

   Create a dense random graph with at least 10 vertices and 15 edges. Then use both Prim's and Kruskal's to determine the minimum spanning tree and compare results.

   Hint

   Compare the number of edges included by each algorithm.