Finding Minimum Spanning Tree Using Kruskal’s Algorithm in CPlusPlus

The Minimum Spanning Tree (MST) is a fundamental concept in graph theory with numerous applications, including network design, clustering, and more. Kruskal’s Algorithm is one of the most efficient algorithms to find the MST of a connected, undirected graph. This article delves into the implementation of Kruskal’s Algorithm in C++, providing a comprehensive explanation of the program structure, detailed documentation, and illustrative examples.

Program Structure

The C++ program to find the MST using Kruskal’s Algorithm is organized into several key components:

• Edge Representation: Struct to represent edges with source, destination, and weight.
• Disjoint Set Union (DSU): Data structure to manage and detect cycles efficiently.
• Kruskal’s Algorithm Implementation: Sorting edges and selecting the smallest edges while avoiding cycles.
• Main Function: Input handling and invoking the MST function.

Code Implementation

The following C++ program implements Kruskal’s Algorithm to find the Minimum Spanning Tree of a graph:

// Kruskal's Algorithm to find Minimum Spanning Tree in C++
// This program finds the MST of a given connected, undirected graph using Kruskal's algorithm.

#include <iostream>
#include <vector>
#include <algorithm&gt>

using namespace std;

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

// Structure to represent a subset for Union-Find
struct Subset {
    int parent;
    int rank;
};

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

// Function to find the set of an element using path compression
int findSet(int i, vector<Subset> &subsets) {
    if (subsets[i].parent != i)
        subsets[i].parent = findSet(subsets[i].parent, subsets);
    return subsets[i].parent;
}

// Function to union two sets using union by rank
void unionSet(int x, int y, vector<Subset> &subsets) {
    int xroot = findSet(x, subsets);
    int yroot = findSet(y, subsets);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// Function to perform Kruskal's algorithm and find MST
vector<Edge> kruskalMST(vector<Edge> &edges, int V) {
    vector<Edge> result; // To store the resultant MST
    int e = 0; // Count of edges in MST

    // Step 1: Sort all the edges in non-decreasing order of their weight
    sort(edges.begin(), edges.end(), compare);

    // Allocate memory for creating V subsets
    vector<Subset> subsets(V);
    for(int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int i = 0; // Index variable for sorted edges

    // Number of edges to be taken is equal to V-1
    while(e < V - 1 && i < edges.size()) {
        // Step 2: Pick the smallest edge. Check if it forms a cycle with the MST so far.
        Edge next_edge = edges[i++];

        int x = findSet(next_edge.src, subsets);
        int y = findSet(next_edge.dest, subsets);

        // If including this edge doesn't cause a cycle, include it in the result
        if(x != y) {
            result.push_back(next_edge);
            unionSet(x, y, subsets);
            e++;
        }
        // Else, discard the edge
    }

    return result;
}

int main() {
    int V, E;
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    vector<Edge> edges(E);
    cout << "Enter the edges in the format (source destination weight):\n";
    for(int i = 0; i < E; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    vector<Edge> mst = kruskalMST(edges, V);

    cout << "\nMinimum Spanning Tree:\n";
    cout << "Edge\tWeight\n";
    for(auto &edge : mst) {
        cout << edge.src << " - " << edge.dest << "\t" << edge.weight << "\n";
    }

    return 0;
}
        

Program Explanation

The program follows Kruskal’s Algorithm to find the Minimum Spanning Tree of a graph. Here’s a breakdown of its components:

1. Edge Representation

Each edge in the graph is represented using the Edge struct, which contains the source vertex (src), destination vertex (dest), and the weight of the edge (weight).

2. Disjoint Set Union (DSU)

The DSU data structure helps in efficiently managing and detecting cycles in the graph. It consists of the Subset struct, which holds the parent and rank of each element.

• findSet Function: Utilizes path compression to find the representative (root) of a set.
• unionSet Function: Merges two sets based on the rank to keep the tree flat, optimizing future operations.

3. Kruskal’s Algorithm Implementation

The kruskalMST function carries out the main steps of Kruskal’s Algorithm:

1. Sort all edges in non-decreasing order of their weight.
2. Initialize DSU for all vertices.
3. Iterate through the sorted edges, and for each edge, check if it forms a cycle using DSU.
4. If it doesn’t form a cycle, include it in the MST and perform a union operation.
5. Continue until the MST contains exactly V-1 edges.

4. Main Function

The main function handles user input for the number of vertices and edges, reads the edge details, invokes the kruskalMST function to compute the MST, and finally outputs the resulting MST edges along with their weights.

Program Documentation

Detailed documentation for each function and struct in the program:

struct Edge

• Purpose: Represents an edge in the graph.
• Members:
  • int src: Source vertex of the edge.
  • int dest: Destination vertex of the edge.
  • int weight: Weight of the edge.

struct Subset

• Purpose: Represents a subset for the Union-Find algorithm.
• Members:
  • int parent: Parent of the subset.
  • int rank: Rank of the subset for union by rank optimization.

bool compare(Edge a, Edge b)

• Purpose: Comparator function to sort edges in non-decreasing order based on their weight.
• Parameters:
  • Edge a: First edge.
  • Edge b: Second edge.
• Returns: true if a.weight < b.weight, otherwise false.

int findSet(int i, vector<Subset> &subsets)

• Purpose: Finds the representative (root) of the set that element i belongs to, using path compression for optimization.
• Parameters:
  • int i: The element to find the set for.
  • vector<Subset> &subsets: The list of subsets.
• Returns: The representative of the set containing element i.

void unionSet(int x, int y, vector<Subset> &subsets)

• Purpose: Unites two subsets into a single subset using union by rank optimization.
• Parameters:
  • int x: Representative of the first subset.
  • int y: Representative of the second subset.
  • vector<Subset> &subsets: The list of subsets.

vector<Edge> kruskalMST(vector<Edge> &edges, int V)

• Purpose: Implements Kruskal’s Algorithm to find the MST of a graph.
• Parameters:
  • vector<Edge> &edges: List of all edges in the graph.
  • int V: Number of vertices in the graph.
• Returns: A vector of edges that form the Minimum Spanning Tree.

int main()

• Purpose: Entry point of the program. Handles input and output operations.
• Process:
  1. Prompts the user to enter the number of vertices and edges.
  2. Reads the edges along with their weights.
  3. Calls kruskalMST to compute the MST.
  4. Displays the edges in the MST along with their weights.
• Returns: 0 upon successful execution.

How the Program Works

1. Input Handling: The program begins by taking user input for the number of vertices (V) and edges (E). It then reads each edge’s source, destination, and weight.
2. Sorting Edges: All edges are sorted in non-decreasing order based on their weights using the sort function and the compare comparator.
3. Initializing Subsets: Each vertex is initially in its own subset. The subsets vector is initialized accordingly.
4. Building MST: The program iterates through the sorted edges, selecting the smallest edge that doesn’t form a cycle (checked using DSU). Selected edges are added to the MST.
5. Output: Once the MST is formed with exactly V-1 edges, the program outputs the edges included in the MST along with their weights.

Example Execution

Consider the following example graph:

Enter the number of vertices: 4
Enter the number of edges: 5
Enter the edges in the format (source destination weight):
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4
        

Running the program with the above input will produce the following output:

Minimum Spanning Tree:
Edge	Weight
2 - 3	4
0 - 3	5
0 - 1	10
        

This indicates that the MST includes the edges (2-3) with weight 4, (0-3) with weight 5, and (0-1) with weight 10, totaling a minimum weight of 19.

Conclusion

Kruskal’s Algorithm is a powerful method for finding the Minimum Spanning Tree of a graph. By leveraging the Disjoint Set Union data structure for efficient cycle detection and ensuring that the smallest edges are selected first, the algorithm guarantees an optimal MST. This C++ implementation provides a clear and efficient approach to solving the MST problem, suitable for both educational purposes and practical applications in various domains such as network design and clustering.