Kruskal's Algorithm

A greedy algorithm to find MST of a graph. Sorts all edges by increasing weights and adds them one by one to the MST, ensuring that no cycles are formed.

Steps

1. Sort Edges: All edges are sorted by their weights in ascending order.
2. Initialize Union-Find: To manage the connected components of the graph.
3. Iterate through edges: For each edge in the sorted list:
   • Check if the edge connects two different components using the Union-Find structure.
   • If it does, add the edge to the MST and merge the two components.
   • If it forms a cycle, skip the edge.
4. Stop When MST is Complete: The algorithm stops when the MST contains exactly $V - 1$ edges

Implementation

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

using namespace std;

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

// Comparator function to sort edges by weight in non-decreasing order
bool compareEdges(const Edge &a, const Edge &b) {
    return a.weight < b.weight;
}

// Union-Find data structure to detect cycles
class UnionFind {
    vector<int> parent, rank;

public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]); // Path compression
        }
        return parent[u];
    }

    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU == rootV) {
            return false; // Cycle detected
        }

        // Union by rank
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }

        return true;
    }
};

// Function to implement Kruskal's Algorithm to find the MST
void kruskalMST(int V, vector<Edge> &edges) {
    // Step 1: Sort all edges in non-decreasing order of their weight
    sort(edges.begin(), edges.end(), compareEdges);

    UnionFind uf(V);
    vector<Edge> result; // To store the edges included in the MST

    // Iterate through all sorted edges
    for (const auto &edge : edges) {
        // Check if adding this edge forms a cycle
        if (uf.unionSets(edge.src, edge.dest)) {
            result.push_back(edge); // Include the edge in the MST
        }

        // Stop if we already have V-1 edges in the MST
        if (result.size() == V - 1) {
            break;
        }
    }

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

int main() {
    int V = 6;
    vector<Edge> edges = {
        {0, 1, 1}, {1, 2, 2}, {0, 4, 3}, {0, 3, 4},
        {1, 4, 5}, {2, 5, 6}, {3, 4, 7}, {4, 5, 8}
    };

    kruskalMST(V, edges);

    return 0;
}

Example

1. Sort the edges by weight:

   • (A-B, 1), (B-C, 2), (A-E, 3), (A-D, 4), (B-E, 5), (C-F, 6), (D-E, 7), (E-F, 8)

2. Add edges to the MST, ensuring no cycles are formed:

   • Add (A-B, 1)
   • Add (B-C, 2)
   • Add (A-E, 3)
   • Add (A-D, 4)
   • Add (C-F, 6)

The resulting MST will have the edges: (A-B, 1), (B-C, 2), (A-E, 3), (A-D, 4), (C-F, 6).

Time and Space Complexity

Time Complexity

1. Sorting all edges: Takes $O(E \log E)$. Since $E \log E$ is equivalent to $O(E \log V)$ in a connected graph, this step dominates the overall complexity.
2. Union-Find operations: The union-find data structure is used to detect cycles and merge sets. Each union or find operation has an amortized time complexity of $O(\alpha(V))$, where $\alpha(V)$ is the inverse Ackermann function, which grows extremely slowly. For $E$ edges, the total complexity of union-find operations is $O(E \alpha(V))$.

Thus, the overall time complexity of Kruskal’s Algorithm is: $O(E \log E + E \alpha(V)) \approx O(E \log V)$. $$

Space Complexity

1. Edge list: $O(E)$ is required to store all edges.
2. Union-Find data structure: The parent and rank arrays used in the union-find operations require $O(V)$ space.

Therefore, the total space complexity is: $O(E + V)$. $$