Kruskal’s Algorithm

Last Updated on March 2, 2023 by Prepbytes

In this article, we will study about Kruskal algorithm, its implementation, spanning tree, minimum spanning tree, and time complexity of this algorithm.

What is a Spanning Tree?

A spanning tree is a subset of a connected graph G in which every edge is connected, allowing traversal to any edge from a specific edge with or without intermediates. A spanning tree must also be free of cycles. So if the graph has N vertices then the Spanning tree should have N-1 edges.

What is a Minimum Spanning Tree?

The spanning tree which has the least weight or minimum weight spanning tree (i.e. the sum of weights of all the edges is minimum)of all possible spanning trees and this spanning tree is minimum spanning tree.

Application of Minimum Spanning Tree

In the architecture of networks, such as computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids, minimum-spanning trees have practical applications

Kruskal Algorithm

A greedy Algorithm which is used to determine the graph’s minimum spanning tree The algorithm’s primary goal is to identify the subset of edges that will allow us to pass through each graph vertex. Instead of concentrating on a global optimum, it adopts a greedy strategy that seeks the best outcome at each stage. To apply this algorithm graph must be undirected weighted and connected.

Practical Application

• Wiring between cities can be laid out using Kruskal’s algorithm.
• LAN connection

Example
We take an undirected, weighted graph and we find the minimum spanning tree step by step by simply sort the edges in non decreasing. Then pick the edges one by one greedily without forming the cycle.

 
#include <bits/stdc++.h>
using namespace std;
 

 
class DSU {
    int* parent;
    int* rank;
 
public:
    DSU(int n)
    {
        parent = new int[n];
        rank = new int[n];
 
        for (int i = 0; i < n; i++) {
            parent[i] = -1;
            rank[i] = 1;
        }
    }
 
    // Find function
    int find(int i)
    {
        if (parent[i] == -1)
            return i;
 
        return parent[i] = find(parent[i]);
    }
 
    // Union function
    void unite(int x, int y)
    {
        int s1 = find(x);
        int s2 = find(y);
 
        if (s1 != s2) {
            if (rank[s1] < rank[s2]) {
                parent[s1] = s2;
            }
            else if (rank[s1] > rank[s2]) {
                parent[s2] = s1;
            }
            else {
                parent[s2] = s1;
                rank[s1] += 1;
            }
        }
    }
};
 
class Graph {
    vector<vector<int> > edgelist;
    int V;
 
public:
    Graph(int V) { this->V = V; }
 
    void addEdge(int x, int y, int w)
    {
        edgelist.push_back({ w, x, y });
    }
 
    void kruskals_mst()
    {
        // AS WE KNOW KRUSKA IS GREEDY ALGO 
        // WE SIMPLY SORT THE EDGES
        sort(edgelist.begin(), edgelist.end());
 
       
        DSU s(V);
        int ans = 0;
        cout << "Following are the edges in the "
                "constructed MST"
             << endl;
        for (auto edge : edgelist) {
            int w = edge[0];
            int x = edge[1];
            int y = edge[2];
 
           
            if (s.find(x) != s.find(y)) {
                s.unite(x, y);
                ans += w;
                cout << x << " -- " << y << " == " << w
                     << endl;
            }
        }
 
        cout << "Minimum Cost Spanning Tree: " << ans;
    }
};
 

int main()
{
   
    Graph g(7);
    g.addEdge(0, 1, 3);
    g.addEdge(0, 3, 6);
    g.addEdge(1, 4, 3);
    g.addEdge(2, 3, 2);
    g.addEdge(2, 1, 1);
    g.addEdge(2, 4, 6);
    g.addEdge(2, 5, 4);
    g.addEdge(2, 4, 6);
    g.addEdge(3, 5, 2);
    g.addEdge(3, 6, 4);
 
    // Function call
    g.kruskals_mst();
    return 0;
}

Output:

Following are the edges in the constructed MST
2 -- 1 == 1
2 -- 3 == 2
3 -- 5 == 2
0 -- 1 == 3
1 -- 4 == 3
3 -- 6 == 4
Minimum Cost Spanning Tree: 15

Explanation:
First we sort all the edges in non-decreasing order of their weight and then we do greedily pick the edges means we simply pick the edges which have a minimum weight.
Then simply add these edges, and we use a union-find algorithm to detect the cycle.First, we simply pick the edges which have minimum weight and add the edges if after adding these edges form cycle. then we reject the edge for the tree. After getting all the vertices in our tree and this tree is a Minimum spanning tree. This is how this algorithm works.

Kruskal’s Algorithm Time Complexity

O(ElogE) or O(ElogN), here E denotes no of edges and N denotes the total no of vertices. Sorting of edges takes O(ELogE) time. After sorting, we traverse through all edges and apply the find-union algorithm. The find and union operations can take at most O(log N) time. So overall complexity is O(ELogE + ELogN) time. The value of E can be at most O(N2), so O(log N) is O(LogE) the same. Therefore, the overall time complexity is O(E log E) or O(E log N)

Summary
Kruskal’s algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph. It starts with an empty forest and iteratively adds edges to it, always choosing the edge with the lowest weight that does not form a cycle. The process stops when all the vertices are connected in a single tree. Kruskal’s algorithm is based on the observation that a minimum spanning tree of a graph can be found by adding edges in increasing order of weight, as long as they do not form a cycle. It runs in time O(E log E) where E is the number of edges in the graph.