Kruskal's Algorithm

Algorithm for finding the minimum spanning tree (MST) of a weighted graph

Introduction

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph. It works by sorting all edges by weight and adding the smallest edge to the MST, ensuring no cycles are formed using the Union-Find (Disjoint Set) approach.

In Kruskal’s Algorithm, keep two things in mind:

  1. Sort all edges by weight in ascending order.
  2. Connect two nodes only if they aren’t already connected by any path (Using DSU).

How Kruskal's Algorithm Works?

1

Sort all edges in ascending order based on weight.

2

Process each edge in sorted order.

  • Connect the edges if they aren't already connected by any path.
3

Repeat until all edges are processed.

4

Return the MST or its total weight.

Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7
Carousel image 8
Carousel image 9

Implementation

//kruskal'salgorithm.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}

void Union(int x, int y, vector<int> &parent, vector<int> &rank)
{
int x_parent = find(x, parent);
int y_parent = find(y, parent);
if (x_parent == y_parent)
    return;

if (rank[x_parent] > rank[y_parent])
{
    parent[y_parent] = x_parent;
}
else if (rank[x_parent] < rank[y_parent])
{
    parent[x_parent] = y_parent;
}
else
{
    parent[x_parent] = y_parent;
    rank[y_parent]++;
}
}

vector<vector<int>> spanningTree(vector<vector<pair<int, int>>> &adjlist)
{
vector<vector<int>> adj;
for (int u = 0; u < adjlist.size(); u++)
{
    for (auto &neigh : adjlist[u])
    {
        int v = neigh.first;
        int wt = neigh.second;
        adj.push_back({u, v, wt});
    }
}
sort(adj.begin(), adj.end(), [](vector<int> &a, vector<int> &b)
     { return a[2] < b[2]; });

return adj;
}
int kruskal(vector<vector<pair<int, int>>> &adjlist)
{
spanningTree(adjlist);
vector<vector<int>> adj = spanningTree(adjlist);
vector<int> parent(adj.size());
vector<int> rank(adj.size(), 0);
for (int i = 0; i < adj.size(); i++)
{
    parent[i] = i;
}
int sum = 0;
for (auto &temp : adj)
{
    int u = temp[0], v = temp[1], wt = temp[2];
    if (find(u, parent) != find(v, parent))
    {
        Union(u, v, parent, rank);
        sum += wt;
    }
}
return sum;
}
int main()
{
///             0----20-----3-----1-----4
///             |           |           | \      
///             5           5           2  4
///             |           |           |   \       
///             1-----1-----2           5--2--6
vector<vector<pair<int, int>>> adjlist(7);
adjlist[0].push_back({3, 20});
adjlist[0].push_back({1, 5});
adjlist[1].push_back({0, 5});
adjlist[1].push_back({2, 1});
adjlist[2].push_back({1, 1});
adjlist[2].push_back({3, 5});
adjlist[3].push_back({0, 20});
adjlist[3].push_back({2, 5});
adjlist[3].push_back({4, 1});
adjlist[4].push_back({3, 1});
adjlist[4].push_back({5, 2});
adjlist[4].push_back({6, 4});
adjlist[5].push_back({4, 2});
adjlist[5].push_back({6, 2});
adjlist[6].push_back({5, 2});
adjlist[6].push_back({4, 4});
cout<<kruskal(adjlist);
}

Time Complexity

Building Edge list

  • The function spanningTree() converts the adjacency list to an edge list.
  • Iterating over adjlist takes O(V + E) time, where V is the number of vertices and E is the number of edges.
  • Storing the edges in a vector also takes O(E) time.

Sorting the Edge List

  • The edge list is sorted using sort(), which takes O(E log E) time.

Union-Find Operations (With Path Compression & Union by Rank)

  • We initialize parent and rank arrays in O(V) time.
  • Processing each edge requires O(α(V)) (Inverse Ackermann function) for find() and Union(), which is nearly O(1).
  • Since we process at most E edges, this step takes O(E α(V)).

Overall Time Complexity

  • O(E)+O(ElogE)+O(V)+O(Eα(V))
  • The final time complexity is O(ElogE).

Space Complexity

Stores edge list O(E).
Uses parent and rank arrays (DSU) O(V).
Space Complexity O(V+E).