5.3. Tracking Edge Addition

Try these first

1. 1.

   What does Kruskal’s algorithm aim to construct?

   Hint

   Consider what is common in tree structures.

2. 2.

   How does cycle detection work in Kruskal's algorithm?

   Hint

   Think about how components are merged when adding edges.

3. 3.

   What is the main approach used by Kruskal's algorithm?

   • It selects edges randomly
   • It sorts edges and adds the lowest ones
   • It starts from a vertex and grows a tree

   Hint

   Consider how sorting impacts which edges are selected.

4. 4.

   Is Kruskal's algorithm a greedy algorithm?

   • True
   • False

   Hint

   Reflect on what greedy algorithms do.

5. 5.

   Given a graph with the following edges: (1,2,1), (1,3,3), (2,3,2), (2,4,4), (3,4,5). Apply Kruskal's algorithm and outline the steps taken.

   Hint

   Visualize each step by drawing the graph as you add each edge.

6. 6.

   Design a graph where applying Kruskal's algorithm gives a different spanning tree than using Prim's algorithm, justifying the result.

   Hint

   Keep track of selection paths taken by both algorithms.