5.4.2. Outer Loop and Edge Addition

Try these first

1. 1.

   What is the main objective of Kruskal's algorithm?

   Hint

   Think about how it connects all vertices.

2. 2.

   Why is sorting the edges necessary in Kruskal's algorithm?

   Hint

   Consider the greedy approach of the algorithm.

3. 3.

   What is the first step in Kruskal's algorithm?

   • Add edges in random order
   • Sort all edges by weight
   • Select a starting vertex

   Hint

   Think about why we want the least weight edges first.

4. 4.

   True or False: Kruskal's algorithm can create cycles in the minimum spanning tree.

   • True
   • False

   Hint

   Consider the properties of trees.

5. 5.

   Design a graph with at least 6 vertices and 8 edges, demonstrating Kruskal’s algorithm. Show how edges are added step-by-step to form a minimum spanning tree.

   Hint

   Think through sorting and cycle checking at each step.

6. 6.

   Critically evaluate the advantages and disadvantages of Kruskal's algorithm compared to Prim's algorithm.

   Hint

   Consider how each algorithm handles graph connectivity and edge weights.