MST Concepts, Prim vs Kruskal

(i) MST Concept

Connected, undirected, weighted $G(V,E,w)$. Spanning tree $T$ has $V-1$ edges, connects all vertices, acyclic. MST minimizes $\sum_{e\in T} w(e)$; unique if weights distinct. Characterized by Cut Property (lightest edge crossing any cut in some MST) and Cycle Property (heaviest edge on any cycle not in MST). Applications: network design (least cable), clustering.

(ii) Compare Prim vs Kruskal

Feature	Prim	Kruskal
Growth	Vertex-based: grows tree from start vertex, adds min edge crossing cut $(inMST, rest)$.	Edge-based: sorts all edges, adds min edge that doesn't form cycle (Union-Find).
Data structure	Priority queue (heap) + key[].	Union-Find (Disjoint Set) + sorting.
Steps	$V-1$ iterations extract min vertex	$E$ iterations over sorted edges
Complexity	$O(E\log V)$ heap, $O(V^2)$ array (dense), $O(E+V\log V)$ Fibonacci	$O(E\log E)$ sort dominates ($\approx O(E\log V)$ as $\log E ≈ \log V$)
Graph type	Good for dense ($V^2$ edges)	Good for sparse ($E≈V$)
Requires	Connected to get single tree; else spanning forest	Works on forest naturally

Both greedy and optimal via cut property.

(iii) Time & Advantages / Preference

• Prim: $O(V^2)$ without heap best for dense; $O(E\log V)$ with heap. Advantage: single tree growing → early stop or distributed. Preferred when $E$ large, graph dense, or adjacency matrix.
• Kruskal: $O(E\log E)$ sort. Advantage: simple, sorts edges, handles disconnected, easy parallel sort. Preferred when $E$ small (sparse) or edges already sorted.

Overall both $O(E\log V)$; choice depends on density: Prim for dense ($E≫V$), Kruskal for sparse ($E≈V$).