Kruskals MST

#include <bits/stdc++.h> // Includes common standard libraries like iostream, vector, algorithm (for sort), etc.
using namespace std;     // Use the standard namespace.

// Custom comparison function for sorting edges.
// Used by `std::sort` to sort a vector of vectors (representing edges).
// Each inner vector `a` or `b` is expected to be `{u, v, weight}`.
// We want to sort based on the weight, which is at index 2.
bool compare(vector<int> &a, vector<int> &b) {
    return a[2] < b[2]; // Returns true if weight of 'a' is less than weight of 'b'.
}

// ----------------------------------------------------------------------------------
// Disjoint Set Union (DSU) / Union-Find Operations
// These are fundamental for Kruskal's to detect cycles.
// ----------------------------------------------------------------------------------

// findParent: Finds the representative (root) of the set to which 'node' belongs.
// Implements Path Compression for optimization.
// 'parent': The array where parent[i] stores the parent of node i.
// 'node': The current node whose representative needs to be found.
int findParent(vector<int> &parent, int node) {
    // Base Case: If the node is its own parent, it's the root of its set.
    if(parent[node] == node) {
        return node;
    }

    // Recursive Step (Going upwards in hierarchy):
    // Path Compression Logic:
    // During the recursive call, assign the returned root directly to `parent[node]`.
    // This flattens the tree by making all nodes in the path point directly to the root,
    // making future `find` operations for these nodes much faster.
    return parent[node] = findParent(parent, parent[node]);
}

// unionSet: Merges the sets containing 'u' and 'v' using Union by Rank optimization.
// 'u', 'v': The two nodes whose sets are to be merged.
// 'parent': The parent array.
// 'rank': The rank array (stores approximate height of trees).
void unionSet(int u, int v, vector<int> &parent, vector<int> &rank) {
    // Find the representatives (roots) of the sets containing 'u' and 'v'.
    // These will already be 'compressed' if findParent uses path compression.
    u = findParent(parent, u);
    v = findParent(parent, v);

    // If 'u' and 'v' are already in the same set (have the same root), do nothing.
    // This check is typically done *before* calling unionSet in Kruskal's.
    if(u == v) {
        return; // Already in the same component.
    }

    // Union by Rank: Attach the root of the smaller rank tree under the root of the larger rank tree.
    // This helps in keeping the overall tree height minimal, improving findParent performance.
    if(rank[u] < rank[v]) {
        parent[u] = v; // Make 'v' the parent of 'u'.
    } else if(rank[v] < rank[u]) {
        parent[v] = u; // Make 'u' the parent of 'v'.
    } else {
        // If ranks are equal, either can be parent. Choose 'u' to be parent of 'v'.
        parent[v] = u;
        rank[u]++; // Increment the rank of the new root 'u' because its height effectively increased.
    }
}

// ----------------------------------------------------------------------------------
// Kruskal's Algorithm Implementation
// ----------------------------------------------------------------------------------

// calculateKruskalsMST: Calculates the total weight of the Minimum Spanning Tree using Kruskal's algorithm.
// 'edges': A vector of vectors, where each inner vector is {u, v, w} representing an edge.
// 'n': Total number of nodes in the graph (0 to n-1).
// Returns the total minimum weight of the MST.
int calculateKruskalsMST(vector<vector<int>> &edges, int n) {
    // 1. Initialize Disjoint Set Union (DSU) structure.
    // 'parent' array: Each node is initially its own parent.
    // 'rank' array: Initial rank of each set is 0.
    vector<int> parent(n);
    vector<int> rank(n);
    for(int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    // 2. Sort all edges by their weights in non-decreasing order.
    // This is the crucial greedy step of Kruskal's.
    sort(edges.begin(), edges.end(), compare);

    // 'minWeight' will store the sum of weights of edges included in the MST.
    int minWeight = 0;

    // 3. Iterate through the sorted edges.
    for(int i = 0; i < edges.size(); i++) {
        int u_node = edges[i][0]; // Source node of the current edge.
        int v_node = edges[i][1]; // Destination node of the current edge.
        int weight = edges[i][2]; // Weight of the current edge.

        // Find the representatives (roots) of the sets containing u_node and v_node.
        int rootU = findParent(parent, u_node);
        int rootV = findParent(parent, v_node);

        // Check for cycle: If the roots are different, adding this edge will NOT form a cycle.
        if(rootU != rootV) {
            // Merge the sets of u_node and v_node.
            unionSet(rootU, rootV, parent, rank);
            // Add the weight of this edge to the total MST weight.
            minWeight += weight;

            // If you needed to return the MST edges themselves, you would add {u_node, v_node, weight}
            // to a separate result vector here.
        }
        // If rootU == rootV, adding this edge would form a cycle, so we skip it.
    }

    return minWeight; // Return the total weight of the Minimum Spanning Tree.
}

// ----------------------------------------------------------------------------------
// Main Function for input/output.
// ----------------------------------------------------------------------------------

int main() {
    vector<vector<int>> edges; // Stores input edges as {u, v, w}.
    int n, m;                 // 'n' for number of nodes, 'm' for number of edges.

    cout << "Enter the number of nodes : ";
    cin >> n;

    cout << "Enter the number of edges : ";
    cin >> m;

    cout << "Enter the edges (u v w): " << endl;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;         // Read source, destination, and weight.
        edges.push_back({u, v, w}); // Add edge to vector.
    }

    // Calculate the total weight of the Kruskal's MST.
    int minWeight = calculateKruskalsMST(edges, n);

    cout << "Weight of Kruskal's MST : " << minWeight << endl;

    return 0; // Indicate successful execution.
}

1. Problem Statement

• Goal: Find a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.
• MST Definition: A spanning tree that connects all vertices using V-1 edges, without cycles, and with the minimum possible total edge weight.
• Input: A list of weighted edges (u, v, w), and the total number of n nodes. The number of edges m is implicitly handled by the edges.size().
• Output: The total minimum weight of the MST. (The code currently returns only the total weight, not the edges themselves).

2. Core Idea (Kruskal’s Algorithm - Greedy Approach)

Kruskal’s algorithm is a greedy algorithm that builds the MST by considering edges in increasing order of their weights. It uses the Disjoint Set Union (DSU) data structure to efficiently detect and prevent cycles.

• Sort Edges: All edges are sorted in non-decreasing order of their weights.
• Iterate and Add: Iterate through the sorted edges. For each edge (u, v, w):
  • Cycle Check: Use DSU’s findParent operation to check if u and v are already in the same connected component (i.e., if adding this edge would form a cycle).
  • Add to MST: If u and v are in different components, add this edge to the MST. Update the total MST weight. Then, use DSU’s unionSet operation to merge the components of u and v.
  • Skip: If u and v are already in the same component, skip this edge as it would form a cycle.
• Termination: The algorithm stops when N-1 edges have been added to the MST (for a connected graph with N nodes), or when all edges have been processed.

3. Key Components and Algorithm Steps

A. Disjoint Set Union (DSU) Functions (Reused from previous notes)

• findParent(vector<int> &parent, int node):
  • Finds the representative (root) of the set containing node.
  • Path Compression Optimization: Flattens the tree by making all nodes in the path point directly to the root, optimizing future find calls.
• unionSet(int u, int v, vector<int> &parent, vector<int> &rank):
  • Merges the sets containing u and v.
  • Union by Rank Optimization: Attaches the root of the shorter tree to the root of the taller tree to keep the overall tree height small.

B. Edge Comparison Function (compare)

• bool compare(vector<int> &a, vector<int> &b):
  • A custom comparison function used with std::sort.
  • It takes two edge representations (e.g., vector<int> where a[2] is weight) and returns true if a should come before b in sorted order based on their weights. (a[2] < b[2]).

C. calculateKruskalsMST(vector<vector<int>> &edges, int n) Function

1. Initialize DSU:

   • Create vector<int> parent(n) and vector<int> rank(n).
   • For each node i from 0 to n-1: parent[i] = i (each node starts in its own set), rank[i] = 0.

2. Sort Edges:

   • sort(edges.begin(), edges.end(), compare); Sorts all input edges by their weights in non-decreasing order.

3. Initialize MST Weight:

   • int minWeight = 0; (This variable will accumulate the total weight of edges added to the MST).

4. Iterate Through Sorted Edges:

   • Loop through each edge edges[i] in the sorted edges vector:
     • Extract u = edges[i][0], v = edges[i][1], w = edges[i][2].
     • Cycle Check: Find the representatives of u and v: rootU = findParent(parent, u) and rootV = findParent(parent, v).
     • If no cycle (different roots):
       • unionSet(rootU, rootV, parent, rank); (Merge the sets of u and v).
       • minWeight += w; (Add the edge’s weight to the total MST weight).
     • If cycle (same roots):
       • Do nothing, as adding this edge would create a cycle.

5. Return: minWeight (the total weight of the MST).

4. Time and Space Complexity

• Time Complexity: O(E log E + E α(V))
  • Sorting edges: O(E log E) (where E is the number of edges).
  • DSU operations: E times findParent and unionSet operations. With path compression and union by rank, this is O(E α(V)) (where α is the inverse Ackermann function, practically constant).
  • Total: Dominated by sorting, so O(E log E) or O(E log V) (since E <= V^2, log E is at most 2 log V).
• Space Complexity: O(V + E)
  • parent and rank arrays: O(V).
  • Storing edges: O(E).

5. Important Notes

• Connectivity: Kruskal’s algorithm assumes the graph is connected. If the graph is not connected, it will find a Minimum Spanning Forest (a set of MSTs for each connected component). The returned minWeight would be the sum of weights of all such MSTs.
• Edge List Input: Kruskal’s algorithm is naturally suited for graphs represented by an edge list, as it requires sorting all edges.
• Outputting MST Edges: The provided code only sums the total weight. To get the actual edges of the MST, you would store the (u, v, w) of the edges that satisfy u != v in a separate vector before returning.

---