# Kruskal Algorithm  Difficulty Level Hard
Depth First Search Union Find

## What is Kruskal Algorithm?  Kruskal’s algorithm is used to find the minimum spanning tree(MST) of a connected and undirected graph.

### Example

Graph Minimum Spanning Tree(MST) ## Algorithm  Kruskal’s algorithm is a greedy algorithm to find the minimum spanning tree.

1. Sort the edges in ascending order according to their weights.
2. At every step, choose the smallest edge(with minimum weight). If this edge forms a cycle with the MST formed so far, discard the edge, else, add it to the MST.
3. Repeat step 2, until all the vertices are not present in MST.

## Explanation  Consider the graph shown in above example,

The edges in the above graph are,
Edges = {{0 to 1, wt = 5}, {0 to 2, wt = 8}, {1 to 2, wt = 10}, {1 to 3, wt = 15}, {2 to 3, wt = 20}}

After sorting, edges are,
Edges = {{0 to 1 wt = 5}, {0 to 2, wt = 8}, {1 to 2, wt = 10}, {1 to 3, wt = 15}, {2 to 3, wt = 20}}

• {0 to 1, wt = 5}, include in MST • {0 to 2, wt = 8}, include in MST • {1 to 2, wt = 10}, forms a cycle, do not include in MST
• {1 to 3, wt = 15}, include in MST All the vertices are included in MST, so we stop here.

Breadth First Search (BFS) for a Graph

### JAVA Program For Kruskal Algorithm

```public class KruskalAlgorithm {
// Function to find the set of element i
private static int find(Subset subsets[], int i) {
// Path Compression
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// Function to perform union of two sets of x and y
private static void Union(Subset subsets[], int x, int y) {
int xRoot = find(subsets, x);
int yRoot = find(subsets, y);

// (Union by Rank)
if (subsets[xRoot].rank < subsets[yRoot].rank) {
subsets[xRoot].parent = yRoot;
} else if (subsets[xRoot].rank > subsets[yRoot].rank) {
subsets[yRoot].parent = xRoot;
} else {
// If rank are same, then make one as root and increment
// its rank by one
subsets[yRoot].parent = xRoot;
subsets[xRoot].rank++;
}
}

private static void findPrintMST(ArrayList<Edge> graph[], Edge edges[]) {
// Sort the edges in ascending order of their weights
Arrays.sort(edges, Edge.comp);

// Stores the mst
Edge mst[] = new Edge[graph.length - 1];
for (int i = 0; i < graph.length - 1; i++) {
mst[i] = new Edge(-1, -1, -1);
}
int e = 0;      // Number of edges included in mst

// Create v subsets, v is the number of vertices
Subset subsets[] = new Subset[graph.length];
for (int i = 0; i < graph.length; i++) {
subsets[i] = new Subset();
}
// Initialise parent of all as itself and rank as 0
for (int i = 0; i < graph.length; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}

// One by one traverse all the edges
for (int i = 0; i < edges.length; i++) {
// Find the set of vertices present on this edge
int x = find(subsets, edges[i].from);
int y = find(subsets, edges[i].to);

// If the set is not same(that is, no cycle is formed)
// Add this edge to mst
if (x != y) {
mst[e].from = edges[i].from;
mst[e].to = edges[i].to;
mst[e].weight = edges[i].weight;
Union(subsets, x, y);
e++;
} else {
}

// If all the vertices are included in MST, stop here
if (e == graph.length - 1) {
break;
}
}

// Print the MST
for (int i = 0; i < graph.length - 1; i++) {
System.out.println("From " + mst[i].from + " to " + mst[i].to + " weight " + mst[i].weight);
}
}

public static void main(String[] args) {
// Graph
ArrayList<Edge> graph[] = new ArrayList;
// Stores all the edges of the graph
Edge edges[] = new Edge;
for (int i = 0; i < 4; i++)
graph[i] = new ArrayList<>();

// Make the graph in given example

// Store all the edges of the graph
edges = new Edge(0, 1, 5);
edges = new Edge(0, 2, 8);
edges = new Edge(1, 2, 10);
edges = new Edge(1, 3, 15);
edges = new Edge(2, 3, 20);

// Find MST using Kruskal's Algorithm and print it
findPrintMST(graph, edges);
}

static class Edge {
int from;
int to;
int weight;

public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}

public static final Comparator<Edge> comp = new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
// Sort according to edge weights
return Integer.compare(o1.weight, o2.weight);
}
};
}

// Subset class is used to detect cycle while adding an edge
static class Subset {
int parent;
int rank;
}
}```

### C++ Program For Kruskal Algorithm

```#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

// class representing an Edge of a graph
class Edge {
public:
int from;
int to;
int weight;

Edge(int f, int t, int w) {
from = f;
to = t;
weight = w;
}
};

// Subset class is used to detect cycle while adding an edge
class Subset {
public:
int parent;
int rank;
};

// Function to find the set of element i
int find(Subset subsets[], int i) {
// Path compression
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// Function to perform union of two sets of x and y
void Union(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

// Union by Rank
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
// If ranks are same, then make one as root and
// increment its rank by one
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

void findPrintMST(vector<Edge> graph[], vector<Edge> &edges, int v) {
// Sort the edges in ascending order of their weights
sort(edges.begin(), edges.end(),
[](const Edge& lhs, const Edge& rhs) {
return lhs.weight < rhs.weight;
});

// Stores the mst
vector<Edge> mst;
int e = 0;      // Number of edges included in mst

// Create v subsets, v is the number of vertices
Subset *subsets = new Subset[(v * sizeof(Subset))];
// Initialise parent of all as itself and rank as 0
for (int i = 0; i < v; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}

// One by one traverse all the edges
for (int i = 0; i < edges.size(); i++) {
// Find the set of vertices present on this edge
int x = find(subsets, edges[i].from);
int y = find(subsets, edges[i].to);

// If the set is not same(that is, no cycle is formed)
// Add this edge to mst
if (x != y) {
Edge curr(edges[i].from, edges[i].to, edges[i].weight);
mst.push_back(curr);
Union(subsets, x, y);
e++;
} else {
}

// If all the vertices are included in MST, stop here
if (e == v - 1) {
break;
}
}

// Print the mst
for (int i = 0; i < mst.size(); i++) {
cout<<"From "<<mst[i].from<<" to "<<mst[i].to<<" weight "<<mst[i].weight<<endl;
}
}

int main() {
vector<Edge> graph;
vector<Edge> edges;

// Make the graph in given example
Edge e1(0, 1, 5);
Edge e2(0, 2, 8);
Edge e3(1, 0, 5);
Edge e4(1, 2, 10);
Edge e5(1, 3, 15);
Edge e6(2, 0, 8);
Edge e7(2, 1, 10);
Edge e8(2, 3, 20);
Edge e9(3, 1, 15);
Edge e10(3, 2, 20);

graph.push_back(e1);
graph.push_back(e2);
graph.push_back(e3);
graph.push_back(e4);
graph.push_back(e5);
graph.push_back(e6);
graph.push_back(e7);
graph.push_back(e8);
graph.push_back(e9);
graph.push_back(e10);

// Edges in the graph
edges.push_back(e1);
edges.push_back(e2);
edges.push_back(e4);
edges.push_back(e5);
edges.push_back(e8);

// Find MST using Kruskal's Algorithm and print it
findPrintMST(graph, edges, 4);

return 0;
}```

Output

```From 0 to 1 weight 5
From 0 to 2 weight 8
From 1 to 3 weight 15```

## Time Complexity  O(E * log(E) + E * log (V)) where E denotes the Number of edges in the graph and V denotes the Number of vertices in the graph.