Kruskal's Algorithm for MST

Problem Explain Kruskal's algorithm for finding the Minimum Spanning Tree of a graph, and describe how you would implement it.

Be ready to discuss

• The greedy strategy: sort every edge by weight ascending, then add each edge unless it would close a cycle, stopping once you hold V-1 edges.
• Union-Find (Disjoint Set Union) as the cycle test: two endpoints already in the same set means adding that edge creates a cycle.
• Union-Find optimisations: path compression on find and union by rank/size, which together give near-constant amortised cost (inverse Ackermann).
• Complexity: O(E log E) dominated by the sort, with the union-find work effectively O(E * alpha(V)); note E log E = E log V for simple graphs.
• Why the greedy choice is correct: the cut property, and the exchange argument that any non-greedy MST can be transformed into the greedy one without increasing weight.
• Kruskal vs Prim: edge-sorted global greedy suits sparse graphs; Prim's vertex-growing greedy with a priority queue suits dense graphs.
• Edge cases: disconnected graphs yield a minimum spanning forest, and equal edge weights mean the MST is not unique.
• Implementation details that trip people up: 0- vs 1-indexed vertices, and initialising parent/rank arrays correctly.