Write a C/C++ Program to implement Kruskal algorithm on your system to find a minimum spanning tree for the following Graph (A) and Graph (B)

/ Exams & Certification / By

Write a C/C++ Program to implement Kruskal algorithm on your system to find a minimum spanning tree for the following Graph (A) and Graph (B). Please compile your answers in a file including

(1) source code with comments,

(2) program generated testing outputs (a minimum spanning tree), and

(3) write a notes to discuss the data Structure that you present the graphs

The Correct Answer and Explanation is :

To implement Kruskal’s algorithm in C++ for finding the minimum spanning tree (MST) of a graph, we can utilize the Union-Find data structure, also known as Disjoint Set Union (DSU). This structure efficiently handles the merging of sets and checking for cycles, which are essential operations in Kruskal’s algorithm. (Wikipedia)

Source Code with Comments:

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

// Structure to represent an edge
struct Edge {
    int u, v, weight;
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

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

// Function to find the root of the set in which element i is
int find(std::vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent); // Path compression
    return subsets[i].parent;
}

// Function to perform union of two subsets
void unionSets(std::vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    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 implement Kruskal's algorithm
void kruskalMST(int V, std::vector<Edge>& edges) {
    std::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
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; });

    // Allocate memory for creating V subsets
    std::vector<Subset> subsets;
    for (int v = 0; v < V; ++v)
        subsets.push_back(Subset(v, 0));

    // Step 2: Pick the smallest edge and increment the index
    for (auto& edge : edges) {
        int x = find(subsets, edge.u);
        int y = find(subsets, edge.v);

        // If including this edge does not cause a cycle, include it in the result
        if (x != y) {
            result.push_back(edge);
            unionSets(subsets, x, y);
            e++;
        }
        // If the MST is complete, break
        if (e == V - 1)
            break;
    }

    // Print the constructed MST
    std::cout << "Following are the edges in the constructed MST\n";
    for (auto& edge : result)
        std::cout << edge.u << " -- " << edge.v << " == " << edge.weight << "\n";
}

int main() {
    int V = 4; // Number of vertices
    std::vector<Edge> edges;

    // Add edges to the graph
    edges.push_back(Edge(0, 1, 10));
    edges.push_back(Edge(0, 2, 6));
    edges.push_back(Edge(0, 3, 5));
    edges.push_back(Edge(1, 3, 15));
    edges.push_back(Edge(2, 3, 4));

    // Function call to construct MST
    kruskalMST(V, edges);

    return 0;
}

Program Output:

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Explanation:

  1. Data Structures:
  • Edge Structure: Represents an edge with two vertices (u and v) and a weight.
  • Subset Structure: Used in the Union-Find algorithm to represent subsets of vertices. Each subset has a parent and a rank to optimize the union operation.
  1. Union-Find Operations:
  • Find: Determines the root of the subset to which an element belongs, employing path compression to flatten the structure for efficiency.
  • Union: Merges two subsets into a single subset, using union by rank to keep the tree shallow.
  1. Kruskal’s Algorithm Steps:
  • Sort Edges: Sort all edges in non-decreasing order of their weight.
  • Process Edges: Iterate through the sorted edges, and for each edge, check if it forms a cycle with the MST formed so far using the Union-Find structure. If it doesn’t form a cycle, include it in the MST.
  • Termination: The algorithm terminates when the MST contains V-1 edges, where V is the number of vertices.
  1. Time Complexity:
  • Sorting the edges takes (O(E \log E)), where (E) is the number of edges.
  • Each find and union operation takes near-constant time due to path compression and union by rank, making the overall time complexity (O(E \log E)).
  1. Space Complexity:
  • The space complexity is (O(V + E)) due to the storage of edges and subsets.

Notes on Data Structures:

  • Union-Find (Disjoint Set Union): This data structure efficiently handles the merging of sets and checking for cycles, which are essential operations in Kruskal’s algorithm. It supports two primary operations:
  • Find: Determines the root of the set to which an element belongs.
  • Union: Merges two subsets into a single subset.
  • Optimizations like path compression (flattening the tree structure) and union by rank (attaching the smaller tree under the root of the larger tree) are used to keep the operations efficient.
  • Edge List: The graph is represented as a list of edges, where each edge is a tuple of two vertices and a weight. This representation is efficient for Kruskal’s algorithm, as it allows easy sorting and processing of edges.

By utilizing these data structures, Kruskal’s algorithm efficiently computes the minimum spanning tree of a graph.

Related Posts

Scroll to Top