Minimum Spanning Trees – Prim’s and Kruskal’s Algorithms
A Minimum Spanning Tree (MST) of a connected, undirected graph is a subgraph that includes all the vertices of the graph with the minimum possible total edge weight. MSTs find applications in various domains, including network design, clustering, and approximate solutions for optimization problems.
Prim’s Algorithm
Prim’s Algorithm is a greedy algorithm that starts with an arbitrary vertex and grows the tree by adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree until all vertices are included. The algorithm maintains two sets of vertices: one in the MST and one outside.
The steps for Prim’s Algorithm are:
- Choose an arbitrary vertex to start.
- While there are vertices outside the MST, repeat:
- Choose the cheapest edge that connects a vertex in the MST to a vertex outside the MST.
- Add the selected edge and the vertex to the MST.
Kruskal’s Algorithm
Kruskal’s Algorithm is another greedy algorithm that builds the MST by adding edges in increasing order of weight until all vertices are included. It uses a disjoint-set data structure to keep track of connected components and avoid forming cycles.
The steps for Kruskal’s Algorithm are:
- Sort all the edges in non-decreasing order of their weights.
- Initialize an empty MST.
- For each edge in the sorted order, if adding the edge to the MST does not form a cycle, add it to the MST.
Example
Consider the following graph:
Using Prim’s Algorithm, if we start from vertex A:
- Choose A as the starting vertex.
- Connect A to B (weight 2).
- Connect B to D (weight 3).
- Connect D to C (weight 4).
- Connect C to E (weight 5).
The MST obtained using Prim’s Algorithm has a total weight of 14.
Using Kruskal’s Algorithm with sorted edges:
- Add edge AB (weight 2).
- Add edge BD (weight 3).
- Add edge CD (weight 4).
- Add edge CE (weight 5).
The MST obtained using Kruskal’s Algorithm also has a total weight of 14.