5.2.2. Example of Kruskal's Algorithm

Try these first

1. 1.

   What is the first step in Kruskal's Algorithm?

   Hint

   Think about how you would arrange a deck of cards.

2. 2.

   What is a Minimum Spanning Tree?

   Hint

   It must connect without creating cycles.

3. 3.

   What is the first operation performed in Kruskal's Algorithm?

   • Sorting edges
   • Adding edges to the tree
   • Finding cycles

   Hint

   Think of how you identify the smallest item.

4. 4.

   True or False: Kruskal's Algorithm can form cycles in its minimum spanning tree.

   • True
   • False

   Hint

   What property must a tree maintain?

5. 5.

   A graph has vertices A, B, C, D, and edges (A-B: 1), (A-C: 3), (B-C: 2), (C-D: 4). Walk through Kruskal's algorithm to find the MST.

   Hint

   Pay attention to what happens when you try to add edges.

6. 6.

   Assuming a graph is fully connected with edge weights 1, 2, 3, and 4. If vertices are A, B, C, and D, find the weights of edges in the minimum spanning tree after applying Kruskal's Algorithm.

   Hint

   Count edges and vertices carefully, and remember to avoid cycles.