Minimum Spanning Tree using Kruskal’s Algorithm | DSA in C++ - Software Development PDF Download

Introduction

In graph theory, a minimum spanning tree (MST) is a subgraph that connects all the vertices of a weighted graph with the minimum possible total edge weight. Kruskal's algorithm is one of the popular algorithms used to find the minimum spanning tree. In this article, we will explore Kruskal's algorithm and its implementation in C++.

Understanding Minimum Spanning Tree:

A minimum spanning tree of a graph is a tree that connects all the vertices of the graph with the minimum possible total edge weight. It has the following properties:

• It is a connected subgraph.
• It contains V-1 edges, where V is the number of vertices in the graph.
• It does not contain any cycles.

Kruskal's Algorithm Overview:

Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree in a connected, undirected graph. The steps involved in Kruskal's algorithm are as follows:

• Sort all the edges of the graph in non-decreasing order of their weights.
• Initialize an empty set to store the minimum spanning tree.
• Iterate through the sorted edges:
  • Add the current edge to the minimum spanning tree if it does not create a cycle.
  • A cycle can be detected using a disjoint set data structure.
• Repeat step 3 until the minimum spanning tree has V-1 edges, where V is the number of vertices.

Implementation of Kruskal's Algorithm in C++:

Data Structures Required:

• Edge structure: To represent an edge with source, destination, and weight.
• Disjoint set data structure: To detect cycles efficiently.

Code Explanation:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Structure to represent an edge

struct Edge {

    int source, destination, weight;

};

// Disjoint set data structure

struct DisjointSet {

    vector<int> parent, rank;

        DisjointSet(int n) {

        parent.resize(n);

        rank.resize(n, 0);

        

        for (int i = 0; i < n; ++i)

            parent[i] = i;

    }

        int find(int x) {

        if (parent[x] != x)

            parent[x] = find(parent[x]);

                return parent[x];

    }

        void unionSets(int x, int y) {

        int rootX = find(x);

        int rootY = find(y);

                if (rank[rootX] < rank[rootY])

            parent[rootX] = rootY;

        else if (rank[rootX] > rank[rootY])

            parent[rootY] = rootX;

        else {

            parent[rootY] = rootX;

            rank[rootX]++;

        }

    }

};

// Kruskal's algorithm function

vector<Edge> kruskalMST(vector<Edge>& edges, int n) {

    // Sort edges in non-decreasing order of their weights

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {

        return a.weight < b.weight;

    });

        vector<Edge> mst;

    DisjointSet ds(n);

        for (const Edge& edge : edges) {

        int sourceRoot = ds.find(edge.source);

        int destinationRoot = ds.find(edge.destination);

                if (sourceRoot != destinationRoot) {

            // Add the edge to the minimum spanning tree

            mst.push_back(edge);

                        // Merge the two sets

            ds.unionSets(sourceRoot, destinationRoot);

        }

    }

        return mst;

}

int main() {

    // Example usage

    int n = 4; // Number of vertices

    vector<Edge> edges = {

        {0, 1, 10},

        {0, 2, 6},

        {0, 3, 5},

        {1, 3, 15},

        {2, 3, 4}

    };

        vector<Edge> minimumSpanningTree = kruskalMST(edges, n);

        cout << "Minimum Spanning Tree Edges:\n";

    for (const Edge& edge : minimumSpanningTree) {

        cout << edge.source << " - " << edge.destination << " (Weight: " << edge.weight << ")\n";

    }

       return 0;

}

Examples and Code Outputs:

Example 1: Consider a graph with 4 vertices and the following edges:

(0, 1, 10)

(0, 2, 6)

(0, 3, 5)

(1, 3, 15)

(2, 3, 4)

The output will be:

Minimum Spanning Tree Edges:

2 - 3 (Weight: 4)

0 - 3 (Weight: 5)

0 - 1 (Weight: 10)

Example 2: Consider a graph with 5 vertices and the following edges:

(0, 1, 2)

(0, 3, 6)

(1, 2, 3)

(1, 3, 8)

(1, 4, 5)

(2, 4, 7)

(3, 4, 9)

The output will be:

Minimum Spanning Tree Edges:

0 - 1 (Weight: 2)

1 - 2 (Weight: 3)

1 - 4 (Weight: 5)

0 - 3 (Weight: 6)

Sample Problems and Solutions:

Problem 1: Given a graph with 6 vertices and the following edges:

(0, 1, 4)

(0, 2, 3)

(1, 2, 1)

(1, 3, 2)

(2, 3, 4)

(2, 4, 2)

(3, 4, 3)

(3, 5, 2)

(4, 5, 4)

Find the minimum spanning tree using Kruskal's algorithm.

The minimum spanning tree edges are:

1 - 2 (Weight: 1)

3 - 5 (Weight: 2)

1 - 3 (Weight: 2)

0 - 2 (Weight: 3)

2 - 4 (Weight: 2)

Problem 2: Given a graph with 4 vertices and the following edges:

(0, 1, 3)

(0, 3, 5)

(1, 2, 1)

(1, 3, 6)

(2, 3, 4)

Find the minimum spanning tree using Kruskal's algorithm.

The minimum spanning tree edges are:

1 - 2 (Weight: 1)

0 - 1 (Weight: 3)

0 - 3 (Weight: 5)

Conclusion

Kruskal's algorithm is an efficient approach to find the minimum spanning tree of a graph. By using the disjoint set data structure and sorting the edges based on their weights, we can construct the minimum spanning tree by adding edges that do not form cycles. Understanding Kruskal's algorithm and its implementation in C++ is crucial for solving graph-related problems efficiently.