Prim’s vs Kruskal’s Algorithm: A Deep Dive into Minimum Spanning Trees

A Minimum Spanning Tree (MST) is a fundamental concept in graph theory and optimization.

A spanning tree is:

• A subset of edges of a graph
• That forms a tree (connected + no cycles)
• And includes every node of the graph

A single graph can have multiple spanning trees.

Get Anmolmeet Singh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Among all spanning trees, the one with the minimum total edge weight is called the Minimum Spanning Tree (MST)

example

Why not brute force?

A brute-force approach would:

1. Generate all possible spanning trees
2. Compute the cost of each
3. Pick the minimum one

This is not practical:

• Number of spanning trees grows exponentially
• Completely infeasible for large graphs

Hence, we use greedy algorithms.

Important properties of MST

• Exists only for connected graphs
• A disconnected graph does not have an MST
• MST always has (V − 1) edges
• MST contains no cycles

Greedy algorithms for MST

Two classical greedy algorithms are used:( code )

1. Prim’s Algorithm
2. Kruskal’s Algorithm

Both produce the same result but differ in approach, data structures, and use cases.

Prim’s Algorithm (Node-based greedy)

Core idea

Start from any node and:

• Repeatedly connect it to the nearest unvisited node
• Ensure no cycle is formed
• Grow the MST node by node

At every step, choose the minimum weight edge that connects:

• A node inside MST → a node outside MST

Implementation approach

• Convert edge list into an adjacency list
• Use a min-heap (priority queue) storing
  {weight, node, parent}
• Maintain a isMST[] array to avoid cycles

Time complexity

Using a priority queue:

• Push operations: O(E log V)
• Pop operations: O(E log V)

Overall:

O(E log V)

When Prim’s is better

• Graph is dense
• You already have an adjacency list
• You want to grow MST from a starting node

Kruskal’s Algorithm (Edge-based greedy)

Core idea

Instead of nodes, Kruskal works on edges:

1. Sort all edges by increasing weight
2. Pick the smallest edge
3. Add it only if it does not form a cycle
4. Stop when MST has V − 1 edges

Cycle detection: the tricky part

Naive approach

Before adding an edge (u, v):

• Check using DFS/BFS if u can already reach v

This takes:

O(V + E) per edge using DFS/BFS, which becomes inefficient for large graphs.

Optimized solution: Disjoint Set (Union-Find)

Key idea

• Each connected component is a set
• If two nodes belong to the same set, adding an edge creates a cycle
• If they belong to different sets, edge is safe

This gives almost O(1) cycle detection.

Disjoint Set optimizations

Data structures

• parent[] → stores immediate parent
• rank[] or size[] → helps keep trees shallow

Operations

1. Find with Path Compression

• Directly attach nodes to root
• Future queries become faster

2. Union by Rank / Size

• Attach smaller tree under larger tree
• Minimizes height

Amortized complexity:

O(α(V))  ≈ constant

Steps of Kruskal using DSU

1. Sort edges by weight (or use min-heap)
2. For each edge (u, v):

• Find ultimate parents pu, pv
• If pu != pv:
• Add edge to MST
• Union the sets
• Else:
• Skip (cycle)

3. Stop when MST has V − 1 edges

Heap vs Direct Sort in Kruskal

Direct sort

• Sort edges once: O(E log E)
• Simpler and faster in practice

Heap / Priority Queue

• Heapify: O(E)
• Extract min repeatedly: O(E log E)
• Allows early stopping
• Useful for dynamic or streaming edges

Final complexity (both)

O(E log E), since α(V) is negligible

Heapify improves constants but does not change Big-O.

Prim vs Kruskal: Comparison

Below are real-world use cases where MST is actually used in practice (not just theoretical):

1. Telecommunication network planning
   ISPs and telecom companies use MST-based models to design fiber-optic and cable layouts that minimize total installation cost
2. Electric power transmission networks
   Utility companies use MST principles while planning high-voltage transmission lines between substations to reduce wiring cost.
3. VLSI & chip routing
   In semiconductor design, MST and Steiner Tree variants are used to minimize total wire length on integrated circuits.
4. Hierarchical clustering (Single-Linkage)
   MST is directly used in single-linkage clustering, applied in bioinformatics, market segmentation, and pattern recognition
5. Image segmentation
   MST helps group pixels into regions based on minimum similarity distance, used in computer vision pipelines.
6. Network backbone design (LAN/WAN)
   Enterprises use MST-like logic to create loop-free, cost-efficient backbone networks.
7. Transportation infrastructure planning
   Used in early-stage road, rail, and metro feasibility planning to estimate minimum connection cost.
8. Pipeline routing (oil, gas, water)
   Engineering firms apply MST models to reduce pipe length and material cost.
9. GIS and map systems
   Used to compute minimum-cost connectivity between geographic points.
10. Approximation algorithms (Steiner Tree, TSP)
    MST acts as a base structure in many real optimization algorithms.

Key point:
MST is not directly deployed as-is everywhere, but it is embedded inside real engineering, networking, ML, and optimization systems as a core building block.

Thanks for Reading!!