5.4.1. Initialization

Try these first

1. 1.

   What does Kruskal's algorithm primarily aim to find in a graph?

   Hint

   Think about the tree with the least weight.

2. 2.

   What is the base step of Kruskal's algorithm?

   Hint

   What do we prioritize in edge selection?

3. 3.

   Kruskal's algorithm adds edges in which order?

   • Random order
   • Ascending order of weights
   • Descending order of weights

   Hint

   Think about how you would minimize a cost.

4. 4.

   True or False: Kruskal's algorithm can form cycles by adding edges.

   • True
   • False

   Hint

   What should happen if edges connect the same component?

5. 5.

   Given the following edges and their weights: (A-B, 3), (B-C, 5), (C-D, 2), (A-D, 4), and (B-D, 8), use Kruskal's algorithm to find the minimum spanning tree. Explain your steps.

   Hint

   What should you do first with the weights?

6. 6.

   Illustrate how the union-find operations can affect the efficiency of Kruskal's algorithm in a large graph with many disjoint components.

   Hint

   Consider how this structure changes the tracking of added edges.