A minimum spanning tree (MST), sometimes know as least weight spanning tree, for a weighted, linked, undirected graph a spanning tree with a weight less than or equal to that of every other spanning tree. See this page to get more about Minimum Spanning Tree.
Kruskal’s Algorithm:
We shall now go over Kruskal’s method to determine the MST of a given weighted graph.
Sort all of the supplied graph’s edges in Kruskal’s method in rising sequence. If the newly added edge does not create a cycle, it then goes on adding fresh edges and nodes in the MST. It selects the largest weighted edge last and the smallest weighted edge first. In every phase, then, we can claim that it makes a locally optimal decision to discover the best answer. This then is a greedy algorithm.
Kruskal’s method for finding MST:
The following describes how to find MST applying Kruskal’s method:
Sort the weight of every edge in non-decreasing sequence.
Choose the weakest edge. Verify whether it creates a cycle using the currently created spanning tree. Add this edge if the cycle isn’t created. Rather, throw it away.
Till the spanning tree has (V-1) edges, repeat step #2.
The greedy method is used in Kruskal’s method of minimal cost spanning tree finding. Choosing the smallest weight edge that does not create a cycle in the MST built thus far is the greedy choice. Allow us to clarify it using a case study:
Illustration:
The graph boasts fourteen edges and nine vertices. The lowest spanning tree so produced will have (9 – 1) = 8 edges.
following sorting:
Weight | Source | Destination |
| 1 | 7 | 6 |
| 2 | 8 | 2 |
| 2 | 6 | 5 |
| 4 | 0 | 1 |
| 4 | 2 | 5 |
| 6 | 8 | 6 |
| 7 | 2 | 3 |
| 7 | 7 | 8 |
| 8 | 0 | 7 |
| 8 | 1 | 2 |
| 9 | 3 | 4 |
| 10 | 5 | 4 |
| 11 | 1 | 7 |
| 14 | 3 | 5 |
Below is the implementation of the above approach:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// DSU data structure
// path compression + rank by union
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; }
// Function to add edge in a graph
void addEdge(int x, int y, int w)
{
edgelist.push_back({ w, x, y });
}
void kruskals_mst()
{
// Sort all edges
sort(edgelist.begin(), edgelist.end());
// Initialize the DSU
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];
// Take this edge in MST if it does
// not forms a cycle
if (s.find(x) != s.find(y)) {
s.unite(x, y);
ans += w;
cout << x << " -- " << y << " == " << w
<< endl;
}
}
cout << "Minimum Cost Spanning Tree: " << ans;
}
};
// Driver code
int main()
{
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.addEdge(2, 0, 6);
g.addEdge(0, 3, 5);
// Function call
g.kruskals_mst();
return 0;
}
C
// C code to implement Kruskal's algorithm
#include <stdio.h>
#include <stdlib.h>
// Comparator function to use in sorting
int comparator(const void* p1, const void* p2)
{
const int(*x)[3] = p1;
const int(*y)[3] = p2;
return (*x)[2] - (*y)[2];
}
// Initialization of parent[] and rank[] arrays
void makeSet(int parent[], int rank[], int n)
{
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// Function to find the parent of a node
int findParent(int parent[], int component)
{
if (parent[component] == component)
return component;
return parent[component]
= findParent(parent, parent[component]);
}
// Function to unite two sets
void unionSet(int u, int v, int parent[], int rank[], int n)
{
// Finding the parents
u = findParent(parent, u);
v = findParent(parent, v);
if (rank[u] < rank[v]) {
parent[u] = v;
}
else if (rank[u] > rank[v]) {
parent[v] = u;
}
else {
parent[v] = u;
// Since the rank increases if
// the ranks of two sets are same
rank[u]++;
}
}
// Function to find the MST
void kruskalAlgo(int n, int edge[n][3])
{
// First we sort the edge array in ascending order
// so that we can access minimum distances/cost
qsort(edge, n, sizeof(edge[0]), comparator);
int parent[n];
int rank[n];
// Function to initialize parent[] and rank[]
makeSet(parent, rank, n);
// To store the minimun cost
int minCost = 0;
printf(
"Following are the edges in the constructed MST\n");
for (int i = 0; i < n; i++) {
int v1 = findParent(parent, edge[i][0]);
int v2 = findParent(parent, edge[i][1]);
int wt = edge[i][2];
// If the parents are different that
// means they are in different sets so
// union them
if (v1 != v2) {
unionSet(v1, v2, parent, rank, n);
minCost += wt;
printf("%d -- %d == %d\n", edge[i][0],
edge[i][1], wt);
}
}
printf("Minimum Cost Spanning Tree: %d\n", minCost);
}
// Driver code
int main()
{
int edge[5][3] = { { 0, 1, 10 },
{ 0, 2, 6 },
{ 0, 3, 5 },
{ 1, 3, 15 },
{ 2, 3, 4 } };
kruskalAlgo(5, edge);
return 0;
}
Python3
# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected,
# undirected and weighted graph
# Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
# Function to add an edge to graph
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# A utility function to find set of an element i
# (truly uses path compression technique)
def find(self, parent, i):
if parent[i] != i:
# Reassignment of node's parent
# to root node as
# path compression requires
parent[i] = self.find(parent, parent[i])
return parent[i]
# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
# Attach smaller rank tree under root of
# high rank tree (Union by Rank)
if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x
# If ranks are same, then make one as root
# and increment its rank by one
else:
parent[y] = x
rank[x] += 1
# The main function to construct MST
# using Kruskal's algorithm
def KruskalMST(self):
# This will store the resultant MST
result = []
# An index variable, used for sorted edges
i = 0
# An index variable, used for result[]
e = 0
# Sort all the edges in
# non-decreasing order of their
# weight
self.graph = sorted(self.graph,
key=lambda item: item[2])
parent = []
rank = []
# Create V subsets with single elements
for node in range(self.V):
parent.append(node)
rank.append(0)
# Number of edges to be taken is less than to V-1
while e < self.V - 1:
# Pick the smallest edge and increment
# the index for next iteration
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
# If including this edge doesn't
# cause cycle, then include it in result
# and increment the index of result
# for next edge
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
# Else discard the edge
minimumCost = 0
print("Edges in the constructed MST")
for u, v, weight in result:
minimumCost += weight
print("%d -- %d == %d" % (u, v, weight))
print("Minimum Spanning Tree", minimumCost)
# Driver code
if __name__ == '__main__':
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
# Function call
g.KruskalMST()
Java
// Java program for Kruskal's algorithm
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class KruskalsMST {
// Defines edge structure
static class Edge {
int src, dest, weight;
public Edge(int src, int dest, int weight)
{
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
// Defines subset element structure
static class Subset {
int parent, rank;
public Subset(int parent, int rank)
{
this.parent = parent;
this.rank = rank;
}
}
// Starting point of program execution
public static void main(String[] args)
{
int V = 4;
List<Edge> graphEdges = new ArrayList<Edge>(
List.of(new Edge(0, 1, 10), new Edge(0, 2, 6),
new Edge(0, 3, 5), new Edge(1, 3, 15),
new Edge(2, 3, 4)));
// Sort the edges in non-decreasing order
// (increasing with repetition allowed)
graphEdges.sort(new Comparator<Edge>() {
@Override public int compare(Edge o1, Edge o2)
{
return o1.weight - o2.weight;
}
});
kruskals(V, graphEdges);
}
// Function to find the MST
private static void kruskals(int V, List<Edge> edges)
{
int j = 0;
int noOfEdges = 0;
// Allocate memory for creating V subsets
Subset subsets[] = new Subset[V];
// Allocate memory for results
Edge results[] = new Edge[V];
// Create V subsets with single elements
for (int i = 0; i < V; i++) {
subsets[i] = new Subset(i, 0);
}
// Number of edges to be taken is equal to V-1
while (noOfEdges < V - 1) {
// Pick the smallest edge. And increment
// the index for next iteration
Edge nextEdge = edges.get(j);
int x = findRoot(subsets, nextEdge.src);
int y = findRoot(subsets, nextEdge.dest);
// If including this edge doesn't cause cycle,
// include it in result and increment the index
// of result for next edge
if (x != y) {
results[noOfEdges] = nextEdge;
union(subsets, x, y);
noOfEdges++;
}
j++;
}
// Print the contents of result[] to display the
// built MST
System.out.println(
"Following are the edges of the constructed MST:");
int minCost = 0;
for (int i = 0; i < noOfEdges; i++) {
System.out.println(results[i].src + " -- "
+ results[i].dest + " == "
+ results[i].weight);
minCost += results[i].weight;
}
System.out.println("Total cost of MST: " + minCost);
}
// Function to unite two disjoint sets
private static void union(Subset[] subsets, int x,
int y)
{
int rootX = findRoot(subsets, x);
int rootY = findRoot(subsets, y);
if (subsets[rootY].rank < subsets[rootX].rank) {
subsets[rootY].parent = rootX;
}
else if (subsets[rootX].rank
< subsets[rootY].rank) {
subsets[rootX].parent = rootY;
}
else {
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}
}
// Function to find parent of a set
private static int findRoot(Subset[] subsets, int i)
{
if (subsets[i].parent == i)
return subsets[i].parent;
subsets[i].parent
= findRoot(subsets, subsets[i].parent);
return subsets[i].parent;
}
}
Output
Following are the edges in the constructed MST 2 -- 3 == 4 0 -- 3 == 5 0 -- 1 == 10 Minimum Cost Spanning Tree: 19
Time complexity is O(E * logE) or O(E * logV).
- Edge sorting demands O(E * logE) time.
- We iterate over all edges and use the find-union technique following sorting. At most O(logV), the find and union processes can take.
- Overall complexity then is O(E * logE + E * logV) time.
- O(logV) and O(logE) are the same as E’s value can be at most O(V2). The general temporal complexity is thus O(E * logE) or O(E*logV).
- O(V + E), where V is the graph’s verticle count and E is its edge count.