Minimum Spanning Tree (Prim’s and Kruskal’s)

Minimum Spanning Tree (Prim’s and Kruskal’s)

A Minimum Spanning Tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

Key Concepts

• Spanning Tree: A tree that connects all vertices of a graph.
• Minimum Spanning Tree: A spanning tree with the least total edge weight among all possible spanning trees.

Applications of MST

• Network design (telecommunication, electrical, computer networks)
• Cluster analysis in Machine Learning
• Approximation algorithms for NP-hard problems like TSP
• Designing road or pipeline networks with minimal cost

Example Graph

Vertices: A, B, C, D, E
Edges:
A-B (2), A-C (3), B-C (1), B-D (4), C-D (5), D-E (7)

The MST will connect all vertices (A–E) with the minimum total cost.

1. Kruskal’s Algorithm

Idea:

Kruskal’s algorithm builds the MST by adding edges in increasing order of their weights while avoiding cycles. It uses a Disjoint Set Union (DSU) or Union-Find data structure.

Steps:

1. Sort all edges in non-decreasing order of their weights.
2. Pick the smallest edge. If adding it does not form a cycle, include it in MST.
3. Repeat until there are (V - 1) edges in the MST.

Complexity:

• Sorting edges: O(E log E)
• Union-Find operations: O(E α(V)) ≈ O(E)
• Total: O(E log E)

Example (in brief):

Edges sorted by weight → pick (B–C), (A–B), (B–D), (D–E)
Total MST weight = 2 + 1 + 4 + 7 = 14

2. Prim’s Algorithm

Idea:

Prim’s algorithm starts from one vertex and grows the MST by adding the smallest edge that connects a visited vertex to an unvisited vertex.

Steps:

1. Start from any vertex.
2. Choose the minimum weight edge that connects a visited vertex to an unvisited vertex.
3. Add the new vertex and repeat until all vertices are included.

Complexity:

• Using Min-Heap and Adjacency List: O(E log V)
• Using Adjacency Matrix (simple): O(V²)

Example (in brief):

Start at A → Add edges (A–B), (B–C), (B–D), (D–E)
Total MST weight = 14

Comparison Between Prim’s and Kruskal’s Algorithms

Real-World Example

• Connecting network cables between offices with minimum cost.
• Designing transportation routes.
• Building minimum cost power grids.

Conclusion

Prim’s and Kruskal’s algorithms both find the Minimum Spanning Tree of a weighted graph but differ in approach. Choosing between them depends on the graph’s density and representation. Understanding both is crucial in algorithm design, optimization, and competitive programming.