# Kruskal's Minimum Spanning Tree Algorithm

• Kruskal’s algorithm creates a minimum spanning tree from a weighted undirected graph by adding edges in increasing order of weights.
• Kruskal’s algorithm is greedy in nature as the edges are chosen in the increasing order of their weights.
• The algorithm makes sure that the addition of new edges to the spanning tree does not create a cycle within it.
• A union-by-rank & path compression technique used for merging two disjoint subsets could be used to efficiently add edges to the minimum spanning tree.

Algorithm : Kruskal’s minimum spanning tree ( Graph G )

0.    Create an empty minimum spanning tree M i.e M = ∅ (zero edges)
1.     Sort the edge-list of the graph G in ascending order of weights.
2.    For each edge ( A, B ) in the sorted edge-list.
3.         If Find_Set_Of_A != Find_Set_Of_B, then
4.              Add edge A-B to the minimum spanning tree M i.e M = M + edge ( A - B )
5.              Make a set / union of Find_Set_Of_A + Find_Set_Of_B.

Example of finding the minimum spanning tree using Kruskal’s algorithm

Time complexity of Kruskal’s algorithm : O ( E log ( E ) ) or O ( E log ( V )). Where E is the number of edges and V is the number of vertices.

Why is the time complexity of Kruskal's algorithm O ( E log ( E ) ) or O ( E log ( V ) ) ?

Kruskal’s minimum spanning tree implementation

``````from typing import List # for annotations

class Edge :

def __init__(self, arg_src : int, arg_dst : int, arg_weight : int) :
self.src = arg_src
self.dst = arg_dst
self.weight = arg_weight

class Graph :

def __init__(self, num_nodes : int, edgelist : List[Edge]) :
self.num_nodes = num_nodes
self.edgelist  = edgelist
self.parent    = []
self.rank      = []
# mst stores edges of the minimum spanning tree
self.mst       = []

def FindParent (self, node : int) :
# With path-compression.
if node != self.parent[node] :
self.parent[node] = self.FindParent(self.parent[node])
return self.parent[node]

# Without path compression
# if node == self.parent[node] :
#    return node
# return self.FindParent(self.parent[node])

def KruskalMST (self) :

# Sort objects of an Edge class based on attribute (weight)
self.edgelist.sort(key = lambda Edge : Edge.weight)

self.parent = [None] * self.num_nodes
self.rank   = [None] * self.num_nodes

for n in range(self.num_nodes) :
self.parent[n] = n # Every node is the parent of itself at the beginning
self.rank[n] = 0   # Rank of every node is 0 at the beginning

for edge in self.edgelist :
root1 = self.FindParent(edge.src)
root2 = self.FindParent(edge.dst)

# Parents of the source and destination nodes are not in the same subset
# Add the edge to the spanning tree
if root1 != root2 :
self.mst.append(edge)
if self.rank[root1] < self.rank[root2] :
self.parent[root1] = root2
self.rank[root2] += 1
else :
self.parent[root2] = root1
self.rank[root1] += 1

print("\nEdges of minimum spanning tree in graph :", end=' ')
cost = 0
for edge in self.mst :
print("[" + str(edge.src) + "-" + str(edge.dst) + "](" + str(edge.weight) + ")", end = ' ')
cost += edge.weight
print("\nCost of minimum spanning tree : " +str(cost))

def main() :

# Edge(source, destination, weight)
num_nodes = 6
e1 = Edge(0, 1, 4)
e2 = Edge(0, 2, 1)
e3 = Edge(0, 3, 5)
e4 = Edge(1, 3, 2)
e5 = Edge(1, 4, 3)
e6 = Edge(1, 5, 3)
e7 = Edge(2, 3, 2)
e8 = Edge(2, 4, 8)
e9 = Edge(3, 4, 1)
e10 = Edge(4, 5, 3)

g1 = Graph(num_nodes, [e1, e2, e3, e4, e5, e6, e7, e8, e9, e10])
g1.KruskalMST()

num_nodes = 7
a = Edge(0, 1, 1)
b = Edge(0, 2, 2)
c = Edge(0, 3, 1)
d = Edge(0, 4, 1)
e = Edge(0, 5, 2)
f = Edge(0, 6, 1)
g = Edge(1, 2, 2)
h = Edge(1, 6, 2)
i = Edge(2, 3, 1)
j = Edge(3, 4, 2)
k = Edge(4, 5, 2)
l = Edge(5, 6, 1)

g2 = Graph(num_nodes, [a, b, c, d, e, f, g, h, i, j, k, l])
g2.KruskalMST()

if __name__ == "__main__" :
main()
``````

Output

``````Edges of minimum spanning tree in graph : [0-2](1) [3-4](1) [1-3](2) [2-3](2) [1-5](3)
Cost of minimum spanning tree : 9

Edges of minimum spanning tree in graph : [0-1](1) [0-3](1) [0-4](1) [0-6](1) [2-3](1) [5-6](1)
Cost of minimum spanning tree : 6
``````
``````#include<iostream>
#include<vector>
#include<algorithm>

class Edge {

public:

int node_start;
int node_end;
int weight;
Edge(){}
Edge(int node1, int node2, int wt): node_start(node1), node_end(node2), weight(wt){}
};

bool CompareCost (const Edge a, const Edge b) {
return a.weight < b.weight;
}

class Graph{

private:
int num_nodes;
std :: vector<Edge> edgelist; // edgelist will store the edges of minimum spanning tree
std :: vector<int> parent;
std :: vector<int> rank;

public:
Graph(){}
Graph (int num_nodes)
{
this->num_nodes = num_nodes;
parent.resize(num_nodes);
rank.resize(num_nodes);
}

int FindParent(int node);
void KruskalMST(std :: vector<Edge>&);
void DisplayEdges(std :: vector<Edge>&);
};

void Graph :: AddEdge (Edge e) {
edgelist.push_back(e);
}

int Graph :: FindParent (int node) {

// With path compression
if ( node != parent[node] )
parent[node] = FindParent(parent[node]);
return parent[node];

/* Without path compression
if ( node == parent[node] )
return node;
return FindParent(parent[node]); */
}

void Graph :: DisplayEdges (std :: vector<Edge>& mst) {

int cost = 0;
std :: cout << "Edges of minimum spanning tree : ";
for (auto& e : mst) {
std :: cout << "[" << e.node_start << "-" << e.node_end << "](" << e.weight << ") ";
cost += e.weight;
}
std :: cout << "\nCost of minimum spanning tree : " << cost << std :: endl;
}

//Funtion implements Kruskal's algorithm and finds the minimum spanning tree.
void Graph :: KruskalMST (std :: vector<Edge>& result) {

for (int i=0; i<num_nodes; i++) {
parent[i] = i;
rank[i] = 0;
}
// Sort the edges based on their weights
sort(edgelist.begin(), edgelist.end(), CompareCost);

// Apply union-by-rank technique to find the minimum spanning tree.
for (auto& e : edgelist) {
int root1 = FindParent(e.node_start);
int root2 = FindParent(e.node_end);

if (root1 != root2) {
result.push_back(e);
if (rank[root1] < rank[root2]) {
parent[root1] = root2;
rank[root2]++;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
}

int main() {

int num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

Edge e1(0, 1, 4);
Edge e2(0, 2, 1);
Edge e3(0, 3, 5);
Edge e4(1, 3, 2);
Edge e5(1, 4, 3);
Edge e6(1, 5, 3);
Edge e7(2, 3, 2);
Edge e8(2, 4, 8);
Edge e9(3, 4, 1);
Edge e10(4, 5, 3);

Graph g1(num_nodes);

std :: vector<Edge> mst; // mst will contain the minimum spanning tree
g1.KruskalMST(mst);
g1.DisplayEdges(mst);

num_nodes = 7;

Edge a(0, 1, 1);
Edge b(0, 2, 2);
Edge c(0, 3, 1);
Edge d(0, 4, 1);
Edge e(0, 5, 2);
Edge f(0, 6, 1);
Edge g(1, 2, 2);
Edge h(1, 6, 2);
Edge i(2, 3, 1);
Edge j(3, 4, 2);
Edge k(4, 5, 2);
Edge l(5, 6, 1);

Graph g2(num_nodes);

mst.clear();
g2.KruskalMST(mst);
g1.DisplayEdges(mst);

return 0;
}
``````

Output

``````Edges of minimum spanning tree are : [0-2](1) [3-4](1) [1-3](2) [2-3](2) [1-5](3)
Cost of minimum spanning tree : 9
Edges of minimum spanning tree : [0-1](1) [0-3](1) [0-4](1) [0-6](1) [2-3](1) [5-6](1)
Cost of minimum spanning tree : 6
``````
``````import java.util.ArrayList;
import java.util.List;

class Edge {

int node_start;
int node_end;
int weight;
Edge (int node1, int node2, int wt) {
node_start = node1;
node_end = node2;
weight = wt;
}

public int GetWeight() {
return weight;
}
};

class Graph {

private int num_nodes;
private List<Edge> edgelist = new ArrayList<Edge>(); // Edgelist stores the edges of MST
private List<Integer> parent;
private List<Integer> rank;

Graph (int num_nodes) {
this.num_nodes = num_nodes;
parent = new ArrayList<Integer>(num_nodes);
rank = new ArrayList<Integer>(num_nodes);
}

public void AddEdge (Edge e) {
}

public int FindParent (int node) {

// With path compression
if ( node != parent.get(node) )
parent.set(node, FindParent(parent.get(node)));

return parent.get(node);

/* Without path compression
if ( node == parent.get(node) )
return node;

return FindParent(parent.get(node)); */
}

//Funtion implements Kruskal's algorithm and finds the minimum spanning tree.
public void KruskalMST (List<Edge> result) {

for (int i=0; i<num_nodes; i++) {
parent.add(i, i); // Initially set every node as the parent of itself.
rank.add(i, 0);   // Initial rank of each node is 0.
}

// Lambda expression to sort the edges based on their weights
edgelist.sort((Edge e1, Edge e2)->e1.GetWeight()-e2.GetWeight());

for (Edge e : edgelist) {

int root1 = FindParent(e.node_start);
int root2 = FindParent(e.node_end);
// Union by rank technique to find minimum spanning tree.
if (root1 != root2) {
if (rank.get(root1) < rank.get(root2)) {
parent.set(root1, root2);
rank.set(root2, rank.get(root2) + 1);
} else {
parent.set(root2, root1);
rank.set(root1, rank.get(root1) + 1);
}
}
}
}

public void DisplayEdges(List<Edge> result) {
int cost = 0;
System.out.print( "\nEdges of minimum spanning tree : ");
for (Edge edge : result) {
System.out.print( "[" + edge.node_start + "-" + edge.node_end + "]-(" + edge.weight + ") ");
cost += edge.weight;
}
System.out.println("\nCost of minimum spanning tree : " + cost);
}

public static void main (String args[]) {

int num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

// Edge (source, dest, weight);
Edge e1 = new Edge(0, 1, 4);
Edge e2 = new Edge(0, 2, 1);
Edge e3 = new Edge(0, 3, 5);
Edge e4 = new Edge(1, 3, 2);
Edge e5 = new Edge(1, 4, 3);
Edge e6 = new Edge(1, 5, 3);
Edge e7 = new Edge(2, 3, 2);
Edge e8 = new Edge(2, 4, 8);
Edge e9 = new Edge(3, 4, 1);
Edge e10 = new Edge(4, 5, 3);

Graph g1 = new Graph(num_nodes);

List<Edge> mst = new ArrayList<Edge>();
g1.KruskalMST(mst);
g1.DisplayEdges(mst);

num_nodes = 7;

Edge a = new Edge(0, 1, 1);
Edge b = new Edge(0, 2, 2);
Edge c = new Edge(0, 3, 1);
Edge d = new Edge(0, 4, 1);
Edge e = new Edge(0, 5, 2);
Edge f = new Edge(0, 6, 1);
Edge g = new Edge(1, 2, 2);
Edge h = new Edge(1, 6, 2);
Edge i = new Edge(2, 3, 1);
Edge j = new Edge(3, 4, 2);
Edge k = new Edge(4, 5, 2);
Edge l = new Edge(5, 6, 1);

Graph g2 = new Graph(num_nodes);

mst.clear();
g2.KruskalMST(mst);
g2.DisplayEdges(mst);
}
}
``````

Output

``````Edges of minimum spanning tree : [0-2]-(1) [3-4]-(1) [1-3]-(2) [2-3]-(2) [1-5]-(3)
Cost of minimum spanning tree : 9

Edges of minimum spanning tree : [0-1]-(1) [0-3]-(1) [0-4]-(1) [0-6]-(1) [2-3]-(1) [5-6]-(1)
Cost of minimum spanning tree : 6
``````