19.2.3. Kruskal’s Algorithm

Try these first

1. 1.

   What is a minimum spanning tree?

   Hint

   Think of it as connecting all points with the least cost.

2. 2.

   List the steps of Kruskal's Algorithm.

   Hint

   What are the main stages we discussed?

3. 3.

   What is Kruskal's Algorithm used for?

   • Finding shortest path
   • Minimum spanning tree
   • Sorting algorithms

   Hint

   Consider what it means to connect all vertices with minimum weight.

4. 4.

   True or False: Kruskal's Algorithm can produce more than one minimum spanning tree for a given graph.

   • True
   • False

   Hint

   Think about edges with equal weights.

5. 5.

   Create a graph with weighted edges and apply Kruskal’s Algorithm to find the minimum spanning tree. Describe each step taken.

   Hint

   Use the weights as a guiding principle.

6. 6.

   Compare the efficiency of Kruskal's Algorithm versus Prim's Algorithm in your own words; provide scenarios where each method shines.

   Hint

   Think about the types of graphs you may encounter.