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

A Minimum Spanning Tree (MST) is a subgraph of a weighted graph that:

• Connects all the vertices without forming cycles.
• Has the minimum possible total edge weight among all spanning trees.

MSTs are widely used in network design, circuit design, clustering, and image segmentation. The two most common algorithms for finding an MST are:

• Kruskal’s Algorithm – A greedy algorithm using edge sorting and the union-find data structure.
• Prim’s Algorithm – A greedy algorithm that builds the MST starting from a single node using a priority queue.

In this article, we’ll explore both algorithms, their working principles, C++ implementations, and real-world applications.

1. Kruskal’s Algorithm: Edge-Based Approach

How Kruskal’s Algorithm Works

Kruskal’s algorithm finds an MST by sorting edges and adding them one by one while avoiding cycles. It uses the union-find (disjoint set) data structure to efficiently manage connected components.

Algorithm Steps

1. Sort all edges in ascending order by weight.
2. Initialize the MST with empty edges.
3. Iterate over sorted edges and check if adding an edge forms a cycle:
   • If no cycle is formed, add the edge to the MST.
   • If a cycle is detected (using union-find), discard the edge.
4. Repeat until the MST contains (V – 1) edges, where V is the number of vertices.

C++ Implementation of Kruskal’s Algorithm

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Comparator function to sort edges by weight
bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

// Disjoint Set (Union-Find)
class DisjointSet {
    vector<int> parent, rank;
public:
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    
    int find(int v) {
        if (parent[v] != v)
            parent[v] = find(parent[v]);
        return parent[v];
    }

    void unite(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA != rootB) {
            if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
            else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
            else {
                parent[rootB] = rootA;
                rank[rootA]++;
            }
        }
    }
};

void kruskalMST(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end(), compare);
    DisjointSet ds(V);
    vector<Edge> mst;
    
    for (Edge& edge : edges) {
        if (ds.find(edge.src) != ds.find(edge.dest)) {
            mst.push_back(edge);
            ds.unite(edge.src, edge.dest);
        }
        if (mst.size() == V - 1) break;
    }

    cout << "Minimum Spanning Tree (Kruskal’s Algorithm):\n";
    for (const Edge& e : mst)
        cout << e.src << " - " << e.dest << " : " << e.weight << endl;
}

int main() {
    vector<Edge> edges = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
    };
    int V = 4;
    kruskalMST(edges, V);
    return 0;
}

Time Complexity

• O(E log E) (sorting edges) + O(E α(V)) (union-find operations) → O(E log V).
• Works well for sparse graphs where E ≪ V².

Applications of Kruskal’s Algorithm

✅ Network Design (LAN/WAN setup, electrical grid connections).
✅ Clustering in machine learning (e.g., social network analysis).
✅ Image Segmentation (used in computer vision).

2. Prim’s Algorithm: Node-Based Approach

How Prim’s Algorithm Works

Prim’s algorithm builds the MST incrementally, starting from an arbitrary node and growing the tree one edge at a time.

Algorithm Steps

1. Start from any node and add it to the MST.
2. Use a priority queue (min-heap) to pick the smallest weighted edge that connects the MST to a new node.
3. Mark the new node as visited and continue selecting edges until all nodes are included.

C++ Implementation of Prim’s Algorithm

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii; // (weight, vertex)

void primMST(vector<vector<pii>>& graph, int V) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<bool> inMST(V, false);
    vector<int> parent(V, -1), key(V, INT_MAX);

    pq.push({0, 0});
    key[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        inMST[u] = true;

        for (auto& [weight, v] : graph[u]) {
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({weight, v});
                parent[v] = u;
            }
        }
    }

    cout << "Minimum Spanning Tree (Prim’s Algorithm):\n";
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << " : " << key[i] << endl;
}

int main() {
    int V = 5;
    vector<vector<pii>> graph(V);
    graph[0] = {{2, 1}, {3, 2}};
    graph[1] = {{2, 0}, {3, 2}, {5, 3}};
    graph[2] = {{3, 0}, {3, 1}, {4, 3}, {6, 4}};
    graph[3] = {{5, 1}, {4, 2}, {7, 4}};
    graph[4] = {{6, 2}, {7, 3}};

    primMST(graph, V);
    return 0;
}

Time Complexity

• Using priority queue + adjacency list: O(E log V).
• Best for dense graphs where E ≈ V².

Applications of Prim’s Algorithm

✅ Wireless network design (optimizing signal towers).
✅ Power grids and road networks (minimizing connection costs).
✅ Graph-based clustering (used in AI and ML).

Kruskal vs. Prim: Which One to Use?

Conclusion

Both Kruskal’s and Prim’s algorithms efficiently compute the Minimum Spanning Tree, but they differ in their approaches.

• Kruskal’s is edge-focused and ideal for sparse graphs.
• Prim’s is node-focused and better suited for dense graphs.