How to find a minimum spanning tree using Kruskal's and Prim's algorithms?

**Kruskal's Algorithm (edge-centric):** 1. Sort edges by weight: BC(1), AC(2), DE(2), AB(4), BD(5), DZ(6), CD(8), CE(10), EZ(3) — wait EZ(3) should be before AB. 2. Add BC(1), AC(2), DE(2), EZ(3), AB(4) — but AB would create cycle A-B-C-A, so skip. Add DZ(6). 3. MST edges: BC(1), AC(2), DE(2), EZ(3), DZ(6). Total weight: 14. **Prim's Algorithm (vertex-centric, starting from A):** - A: pick AC(2) → {A, C} - {A, C}: pick CB(1) → {A, B, C} - {A, B, C}: pick BD(5) → {A, B, C, D} - {A, B, C, D}: pick DE(2) → {A, B, C, D, E} - {A, B, C, D, E}: pick EZ(3) → {A, B, C, D, E, Z} Total: 2 + 1 + 5 + 2 + 3 = 13. (Different from Kruskal because Prim picked BD(5) instead of DZ(6). Both are valid MSTs — there can be multiple.) **Why they work (Cut property):** For any cut partitioning vertices into two sets, the minimum-weight edge crossing the cut belongs to some MST. Both algorithms repeatedly apply this property. **Cycle detection in Kruskal:** Use Union-Find (Disjoint Set Union). Each vertex starts in its own set. When adding edge (u, v), check if find(u) = find(v). If so, adding the edge creates a cycle. Otherwise, union the sets. **Time Complexity:** - Kruskal: $O(E \log V)$ (sorting dominates) - Prim (binary heap): $O(E \log V)$ - Prim (Fibonacci heap): $O(V \log V + E)$ **When to use:** - Kruskal: sparse graphs, easy to implement - Prim: dense graphs, especially when adjacency matrix is available