How do I implement minimum spanning tree (Kruskal/Prim) in C++?

The Minimum Spanning Tree (MST) algorithms, including Kruskal's and Prim's, are essential for finding the least-cost paths between nodes in a graph. These algorithms are widely used in networking, circuit design, and various optimization problems.

Kruskal's Algorithm Implementation in C++


#include 
#include 
#include 

using namespace std;

struct Edge {
    int src, dest, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

class DisjointSet {
    vector 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 u) {
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }

    void unionSet(int u, int v) {
        int rootU = find(u), rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

void kruskalMST(vector& edges, int V) {
    sort(edges.begin(), edges.end(), compare);
    DisjointSet ds(V);
    
    vector mstEdges;

    for (Edge e : edges) {
        if (ds.find(e.src) != ds.find(e.dest)) {
            ds.unionSet(e.src, e.dest);
            mstEdges.push_back(e);
        }
    }

    for (Edge e : mstEdges) {
        cout << e.src << " -- " << e.dest << ": " << e.weight << endl;
    }
}

int main() {
    int V = 4; // Number of vertices
    vector edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    kruskalMST(edges, V);
    return 0;
}

Prim's Algorithm Implementation in C++


#include 
#include 
#include 

using namespace std;

#define V 5

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V]; 
    int key[V]; 
    bool mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0; 
    parent[0] = -1; 

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    for (int i = 1; i < V; i++) {
        cout << parent[i] << " -- " << i << ": " << graph[i][parent[i]] << endl;
    }
}

int main() {
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };

    primMST(graph);
    return 0;
}

How do I implement minimum spanning tree (Kruskal/Prim) in C++?

Kruskal's Algorithm Implementation in C++

Prim's Algorithm Implementation in C++

Popular Topics

Recent Languages

How do I implement minimum spanning tree (Kruskal/Prim) in C++?

Kruskal's Algorithm Implementation in C++

Prim's Algorithm Implementation in C++

Related Questions

Popular Topics

Recent Languages