Kruskal's Algorithm

Kruskal's Algorithm for Minimum Spanning Tree (MST)

Kruskal’s algorithm is another greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges. Unlike Prim's algorithm, which grows the MST from a starting vertex, Kruskal's algorithm works by sorting all the edges of the graph and then adding them to the MST one by one, provided they don't form a cycle.

Steps of Kruskal's Algorithm:

1. Sort all edges: Sort the edges of the graph in non-decreasing order of their weights.

2. Initialize:

   • Create a disjoint-set (or union-find) data structure to keep track of the connected components of the graph.
   • Initially, each vertex is its own component (a separate tree).

3. Process each edge:

   • Pick the smallest edge from the sorted list.
   • If the edge connects two different components (i.e., it does not form a cycle), add it to the MST and merge the two components.
   • If adding the edge forms a cycle, discard the edge.

4. Repeat the process until the MST contains exactly V-1 edges (where V is the number of vertices in the graph).

Key Concepts:

• Cycle Detection: Kruskal’s algorithm ensures that no cycles are formed by only adding edges that connect two different components (using a disjoint-set).
• Greedy Choice: At each step, the algorithm picks the smallest weight edge that doesn’t form a cycle, which is a locally optimal choice.

Time Complexity:

• Sorting the edges takes O(E log E) time, where E is the number of edges.
• Using a disjoint-set data structure with union by rank and path compression, each union and find operation takes O(α(V)), where V is the number of vertices, and α is the inverse Ackermann function, which is very small and almost constant.
• The overall time complexity of Kruskal’s algorithm is therefore O(E log E + E α(V)). In most cases, O(E log E) dominates.

Example:

Let’s consider the following graph with 4 vertices and 5 edges:

   10       15
(0)---(1)-------(2)
 |    /  \     |
 5  /     \  4 |
 | /        \  |
(3)---------  (4)
       3

• Vertices: {0, 1, 2, 3, 4}
• Edges and weights:
  • (0, 1, 10)
  • (0, 3, 5)
  • (1, 3, 15)
  • (1, 4, 4)
  • (2, 4, 3)

Steps in Kruskal's Algorithm:

1. Sort the edges in increasing order of their weights:

   • (2, 4, 3)
   • (0, 3, 5)
   • (1, 4, 4)
   • (0, 1, 10)
   • (1, 3, 15)

2. Initialize disjoint-set (each vertex is its own parent):

   • {0}, {1}, {2}, {3}, {4}

3. Pick the smallest edge (2, 4, 3):

   • Vertices 2 and 4 are in different components, so we add this edge to the MST.
   • Merge the components: {2, 4}, {0}, {1}, {3}.

4. Pick the next smallest edge (0, 3, 5):

   • Vertices 0 and 3 are in different components, so we add this edge to the MST.
   • Merge the components: {0, 3}, {2, 4}, {1}.

5. Pick the next smallest edge (1, 4, 4):

   • Vertices 1 and 4 are in different components, so we add this edge to the MST.
   • Merge the components: {1, 4}, {0, 3}, {2}.

6. Pick the next smallest edge (0, 1, 10):

   • Vertices 0 and 1 are already in the same component (merged previously), so adding this edge would form a cycle. We discard this edge.

7. Pick the next smallest edge (1, 3, 15):

   • Vertices 1 and 3 are already in the same component, so adding this edge would form a cycle. We discard this edge.

At this point, we have the MST with the following edges:

• (2, 4, 3)
• (0, 3, 5)
• (1, 4, 4)

Final MST:

The Minimum Spanning Tree contains the edges:

(2, 4, 3)
(0, 3, 5)
(1, 4, 4)

The total weight of the MST is 3 + 5 + 4 = 12.

C++ Code for Kruskal's Algorithm:

Below is the C++ implementation of Kruskal's algorithm using the Union-Find (Disjoint-Set) data structure:

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

using namespace std;

// Edge structure to store the edges
struct Edge {
    int u, v, weight;
};

// Disjoint Set Union-Find structure
class UnionFind {
public:
    UnionFind(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]); // Path compression
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // Union by rank
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector<int> parent, rank;
};

// Function to implement Kruskal's Algorithm
void kruskal(int V, vector<Edge>& edges) {
    // Sort edges based on their weights
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    UnionFind uf(V);

    int mstWeight = 0;
    vector<Edge> mstEdges;

    // Iterate through all edges, picking the smallest edge that doesn't form a cycle
    for (const Edge& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        if (uf.find(u) != uf.find(v)) {
            uf.unite(u, v);
            mstEdges.push_back(edge);
            mstWeight += weight;
        }
    }

    // Print the edges in the MST
    cout << "Edges in the MST:" << endl;
    for (const Edge& edge : mstEdges) {
        cout << "(" << edge.u << ", " << edge.v << ") : " << edge.weight << endl;
    }
    cout << "Total weight of MST: " << mstWeight << endl;
}

int main() {
    int V = 5;  // Number of vertices
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 3, 5},
        {1, 3, 15},
        {1, 4, 4},
        {2, 4, 3}
    };

    // Call Kruskal's algorithm
    kruskal(V, edges);

    return 0;
}

Explanation of the Code:

1. Edge Structure: The Edge structure holds the two vertices (u, v) and the weight of the edge connecting them.

2. Union-Find (Disjoint-Set): The UnionFind class provides methods to perform:

   • find: To find the root of a vertex (with path compression).
   • unite: To merge two sets (using union by rank).

3. Kruskal’s Algorithm:

   • Sorts the edges in ascending order based on their weights.
   • Uses the union-find data structure to add edges to the MST without forming cycles.
   • Prints the edges of the MST and their total weight.

4. Time Complexity:

   • Sorting the edges takes O(E log E) time.
   • Each union and find operation takes O(α(V)) time, where α is the inverse Ackermann function, which is very slow-growing.
   • Thus, the overall complexity is O(E log E + E α(V)).

Final Thoughts:

• Kruskal's algorithm is very effective when the graph is sparse, or when the graph has many edges.