5.2.1. High Level View of the Algorithm

Try these first

1. 1.

   Define a spanning tree.

   Hint

   Consider what it means to connect all vertices.

2. 2.

   What is the main objective of Kruskal's algorithm?

   Hint

   Focus on the cost associated with edges.

3. 3.

   What does Kruskal's algorithm primarily aim to achieve?

   • Find a maximum spanning tree.
   • Find a minimum cost spanning tree.
   • Find a minimum-weight path.

   Hint

   Consider what spanning tree signifies for overall cost.

4. 4.

   True or False: Kruskal's algorithm can add edges that would create cycles in the spanning tree.

   • True
   • False

   Hint

   Remember the basic property of a tree.

5. 5.

   Consider a graph with nodes labeled A to E, and edges with weights between them. Create a minimal spanning tree using Kruskal's algorithm and explain each step.

   Hint

   You may need to visualize the edges while doing this.

6. 6.

   Create a modified version of Kruskal's algorithm that can handle weighted edges with equal importance at each step.

   Hint

   Think about scenarios where edges might have the same weight.