Algorithms

MST: Minimum Spanning Tree

Цели урока

Understand the MST problem
Implement Kruskal with Union-Find
Implement Prim with a priority queue
Know when to use each algorithm

Предварительные знания

Graphs
Union-Find

You're designing an electrical grid for a village. You need to connect all houses with the minimum total wire length. This is the classic MST problem, solved back in 1926!

Network design (electrical, telecommunications)
Data clustering
Approximation algorithm for TSP
Image segmentation

Borůvka's power grid and the algorithms that followed

The MST problem started with a real engineering question. In 1926 the Czech mathematician Otakar Borůvka was asked how to lay out an electrical grid for Moravia using the least total wire, and he published the first MST algorithm to answer it, years before graph theory had settled into a field. His method merges components in parallel rounds, which is why it has come back into fashion for parallel and distributed computing. In 1930 his countryman Vojtěch Jarník described the grow-from-one-vertex approach. That same algorithm was rediscovered by Robert Prim in 1957 and again by Dijkstra in 1959, so 'Prim's algorithm' is more properly Jarník-Prim. Joseph Kruskal published his sort-the-edges approach in 1956 in a four-page paper. Three classic algorithms, three different strategies, all solving the identical problem, and all justified by the same cut property: the lightest edge crossing any cut is safe to add to the MST.

Idea: Connect Everything with Minimum Weight

**Problem:** connect all vertices so that the sum of edge weights is minimal.

**MST properties:**

Contains exactly V-1 edges (it's a tree)
Connects all V vertices
Has the minimum total weight
May not be unique (when weights are equal)

**Greedy choice works!** At each step, pick the 'best' edge - and get a global optimum. This is rare!

An MST for a graph with V vertices contains:

Kruskal's Algorithm

You have a list of all possible roads between cities, sorted by construction cost. Kruskal's approach is beautifully simple: **start building with the cheapest road**. If two cities are already connected (directly or through other roads) - skip that road, it would just create a useless loop. Keep going until all cities are connected.

**Kruskal's idea:** sort edges by weight and greedily include each one if it doesn't form a cycle.

Operation	Complexity
Sort edges	O(E log E)
E Union-Find operations	O(E α(V)) ≈ O(E)
Total	O(E log E) = O(E log V)

Why does Kruskal use Union-Find?

Prim's Algorithm

Picture paint spreading across a map from a single city. At each step, the 'blob' expands to the nearest unpainted city. The connecting edge becomes part of the tree. **Prim's algorithm** works exactly this way - the tree grows like a living organism, always absorbing its nearest neighbor.

**Prim's idea:** grow the tree from one vertex by adding the cheapest edge connecting to the 'cloud'.

Prim Implementation	Complexity
Naive (array)	O(V²)
Binary Heap	O((V + E) log V)
Fibonacci Heap	O(E + V log V)

Prim resembles Dijkstra. What's the difference?

Kruskal vs Prim

	Kruskal	Prim
Approach	Global (all edges)	Local (grow a tree)
Data structure	Union-Find	Priority Queue
Sparse graph	Better: O(E log E)	Worse: O(E log V)
Dense graph	Worse: O(V² log V)	Better: O(V²) naive
Parallelization	Harder	Easier

**Applications of MST:**

**Network design:** minimum cable length
**Clustering:** remove k-1 heaviest MST edges → k clusters
**Approximation algorithms:** TSP approximation via MST
**Computer vision:** image segmentation

For a road network graph (V=10000, E=30000), better to use: