Minimum Spanning Tree Algorithms (Prim's algorithm, Kruskal's algorithm)

A minimum spanning tree (MST) is a tree that connects all vertices of a given graph with the minimum possible total edge weight. It is an essential concept in graph theory and finds applications in various domains such as network design, clustering, and more.

Two popular algorithms for finding minimum spanning trees are Prim's algorithm and Kruskal's algorithm. In this article, we will explore these algorithms and their implementation using the C++ programming language.

Prim's Algorithm

Prim's algorithm starts from an arbitrary vertex and repeatedly adds the shortest edge that connects a vertex in the MST to a vertex outside the MST until all vertices are included. The algorithm maintains a set of vertices in the MST and a set of vertices outside the MST.

The steps involved in Prim's algorithm are as follows:

1. Create a set MSTSet to keep track of vertices included in the MST.
2. Initialize all vertices' keys as INFINITY and set their parent as -1.
3. Choose an arbitrary vertex as the starting vertex and set its key as 0 to include it in the MST.
4. While MSTSet doesn't include all vertices:
   • Choose the vertex u with the minimum key value from the set of vertices not yet included in the MST.
   • Include u in MSTSet.
   • Update the key values of all adjacent vertices of u if they are smaller than their current key values and not included in MSTSet.
   • Set the parent of each adjacent vertex to u.

The final MST can be constructed using the parent array.

Here's the implementation of Prim's algorithm in C++:

#include <iostream>
#include <vector>
#include <climits>

#define V 5

int minKey(const std::vector<int>& key, const std::vector<bool>& mstSet) {
    int min = INT_MAX, min_index = -1;

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

    return min_index;
}

void printMST(const std::vector<int>& parent, const std::vector<std::vector<int>>& graph) {
    std::cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++) {
        std::cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << "\n";
    }
}

void primMST(const std::vector<std::vector<int>>& graph) {
    std::vector<int> parent(V);
    std::vector<int> key(V, INT_MAX);
    std::vector<bool> mstSet(V, 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];
            }
        }
    }

    printMST(parent, graph);
}

int main() {
    std::vector<std::vector<int>> graph = {
        {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;
}

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that builds a minimum spanning tree by repeatedly choosing the edge with the minimum weight from the list of edges and adding it to the MST if it doesn't form a cycle with the existing edges.

The steps involved in Kruskal's algorithm are as follows:

1. Sort all the edges in non-decreasing order of their weight.
2. Initialize an empty graph to store the MST.
3. For each edge (u, v) in the sorted order:
   • If including the edge (u, v) does not form a cycle in the MST, add it to the MST.

The disjoint-set data structure is commonly used to detect cycles efficiently.

Here's the implementation of Kruskal's algorithm in C++:

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

class Edge {
public:
    int src, dest, weight;
};

class Graph {
public:
    std::vector<Edge> edges;
};

bool compareEdges(const Edge& edge1, const Edge& edge2) {
    return edge1.weight < edge2.weight;
}

int findSubset(std::vector<int>& subsets, int i) {
    if (subsets[i] == -1)
        return i;
    return findSubset(subsets, subsets[i]);
}

void unionSubsets(std::vector<int>& subsets, int x, int y) {
    int xroot = findSubset(subsets, x);
    int yroot = findSubset(subsets, y);
    subsets[xroot] = yroot;
}

void kruskalMST(const Graph& graph, int numVertices) {
    std::vector<Edge> result(numVertices);

    std::sort(graph.edges.begin(), graph.edges.end(), compareEdges);

    std::vector<int> subsets(numVertices, -1);

    int e = 0;
    int i = 0;

    while (e < numVertices - 1) {
        Edge nextEdge = graph.edges[i++];

        int x = findSubset(subsets, nextEdge.src);
        int y = findSubset(subsets, nextEdge.dest);

        if (x != y) {
            result[e++] = nextEdge;
            unionSubsets(subsets, x, y);
        }
    }

    std::cout << "Edge \tWeight\n";
    for (i = 0; i < e; i++) {
        std::cout << result[i].src << " - " << result[i].dest << "\t" << result[i].weight << "\n";
    }
}

int main() {
    Graph graph;
    graph.edges = {
        {0, 1, 2}, {0, 3, 6},
        {1, 2, 3}, {1, 3, 8}, {1, 4, 5},
        {2, 4, 7},
        {3, 4, 9}
    };

    int numVertices = 5;

    kruskalMST(graph, numVertices);

    return 0;
}

Conclusion

Prim's algorithm and Kruskal's algorithm are powerful approaches for finding minimum spanning trees in a graph. Both algorithms offer different strategies for constructing an MST and have their own advantages in different scenarios. Understanding these algorithms and their implementation using C++ can be immensely helpful in solving problems related to network design, optimization, and more.