Minimum Spanning Tree: Prim's and Kruskal's Algorithms

Minimum Spanning Tree (MST)

A spanning tree of a connected graph is a subgraph that includes all vertices with the minimum number of edges (V-1) and no cycles. The minimum spanning tree is the spanning tree with the smallest total edge weight.

Properties

• An MST of a graph with V nodes has exactly V-1 edges
• An MST is not unique if multiple edges share the same weight
• The cut property guarantees that the lightest edge crossing any cut belongs to some MST

Kruskal's Algorithm

1. Sort all edges by weight (ascending)
2. Initialize a Union-Find data structure
3. For each edge (in sorted order):
   • If the two endpoints are in different components, add the edge to the MST and union them
   • If they are in the same component, skip (would create a cycle)
4. Stop when V-1 edges have been added

Time: O(E log E) due to sorting

Sorted edges: (A-B, 1), (B-C, 2), (A-C, 3), (C-D, 4)
Add A-B (1), Add B-C (2), Skip A-C (cycle), Add C-D (4)
MST weight: 1 + 2 + 4 = 7

Prim's Algorithm

1. Start from any node, add it to the MST set
2. Among all edges connecting MST nodes to non-MST nodes, pick the lightest
3. Add the selected edge and node to the MST
4. Repeat until all nodes are in the MST

Time: O((V+E) log V) with a priority queue

Kruskal vs Prim

	Kruskal	Prim
Approach	Edge-centric	Node-centric
Data structure	Union-Find	Priority queue
Best for	Sparse graphs	Dense graphs
Graph structure	Works on disconnected (forest)	Requires connected graph