5.1.1. Kruskal's Algorithm

Try these first

1. 1.

   What does Kruskal's Algorithm aim to achieve?

   Hint

   Think about what a spanning tree represents.

2. 2.

   What is the first step in Kruskal's Algorithm?

   Hint

   Consider the sequence of actions in the algorithm.

3. 3.

   What is the main advantage of using Kruskal's Algorithm over other methods?

   • It is always faster
   • It is simpler to implement
   • It guarantees a minimum spanning tree

   Hint

   Consider what the algorithm is specifically designed to achieve.

4. 4.

   True or False: Kruskal's Algorithm can handle disconnected graphs.

   • True
   • False

   Hint

   Reflect on the definition of a spanning tree.

5. 5.

   Given the edge weights of a graph, calculate the minimum cost of connecting all vertices using Kruskal's algorithm.

   Hint

   Use the properties of trees and weights as your guide.

6. 6.

   Consider a graph with edges: A-B(1), A-C(5), B-C(3), B-D(4). Apply Kruskal's Algorithm and identify the minimum spanning tree.

   Hint

   Check sorted order of weights as your first step.