Kruskal’s Algorithm solves the problem of finding a Minimum Spanning Tree(MST) of any given connected and undirected graph.
What is a Minimum Spanning Tree?
It is basically a subgraph of the given graph that connects all the vertices
with minimum number of edges having minimum possible weight with no cycle. As
this graph contains no cycle, that’s why it is called a Tree.
There can be more than one possible
MST depending on the given graph.
For connecting all the vertices in the given graph we need to have atleast vertices1 edges.
Why?
Consider a graph with only two nodes, we can connect these two nodes with one edge. At this point we have, 2 vertices & one edge. Now if we want to include one more vertex in the graph with minimum possible vertices, we need to have an edge going from the current graph to this new vertex to be added. That is, for every incoming node, we need to add an edge.
Therefore both vertices and edges will increase by one and number of vertices
will always be edges+1, this implies, number of edges = vertices1
Algorithm
Kruskal’s is a greedy approach which emphasizes on the fact that we must
include only those (vertices1) edges only in our MST which have minimum
weight amongst all the edges, keeping in mind that we do not include such edge
that creates a cycle in MST
being constructed.
 We keep a list of all the edges sorted in an increasing order according to their weights.

Take an edge from the list, check if it creates a cycle in
the
MST
being constructed, if it does not create any cycle, then we include the edge in our MST being constructed.
 if it creates a cycle, then we skip the current edge and move on to the next edge in the sorted list.

We need to repeat the same process again until we have
(Vertices1)
edges in the final Minimum Spanning Tree.
For all this, We use Disjoint Set Union data structure which helps us in constructing the MST and checking if there exists any cycle in the MST if we include the current edge.
Here’s how we use Disjoint set union to do this :

Initially, every vertex is a
disjoint set
in itself and for adding an edge in between two vertices we need to merge the sets containing these two vertices. 
Every set has their own parent which represents the whole disjoint set and
merging of two sets basically means, making the parents of the
two sets same
. 
Set having lesser number of vertices will merge with the set having higher
number of elements and merging is simply done by making the
parent of bigger set equal to the parent of smaller set.

Now for checking cycle, we see if the current two vertices of the current
edge lie in the
same set or not
.

If they
do not
lie in thesame set
, then it is okay to include this edge in the MST as the two vertices of this current edge are in separate sets and there is exist no path from first vertex to other directly or indirectly, that is why they are intwo DISJOINT sets
, and adding an edge directly from V1 to V2 will not create any cycle. 
If they lie in the
same set
, this means that they are either directly or indirectly connected to each other with minimum number of edges possible(with minimum weights) and adding one more edge will again connect them creating a cycle in theMinimum Spanning Tree
being constructed.
For checking if any two vertices lie in the same set or not,we just need to check the parents/representative of their sets.If they are same, then the two vertices lie in same set or else they lie in different sets
While implementing this algorithm, Along with maintaining a list of sorted
edges, we need to maintain two arrays also, that is, parent array
and size array
, which keeps the tracks of disjoint sets.
Parent array
tells the parent/representative of the set of any ith vertex.Size array
, for any vertex, keeps the track of number of vertices in the disjoint set
of any ith vertex.
Initially, parent of any vertex is that vertex only with the size of its set
equal to 1 as this vertex is the only element in its disjoint set.
that is,Parent[i] = i
size[i] = 1
Consider this graph,
To find the Minimum
Spanning tree of this given bidirectional graph, we first need to sort all the
edges in a nondecreasing order
Sorted list of edges : edge (D, E) with weight = 1 edge (F, E) with weight = 2 edge (A, F) with weight = 3 edge (F, B) with weight = 4 edge (B, E) with weight = 5 edge (A, B) with weight = 6 edge (A, E) with weight = 7 edge (C, E) with weight = 8 edge (D, C) with weight = 8 edge (B, C) with weight = 9 Parent = {0, 1, 2, 3, 4, 5} Size = {1, 1, 1, 1, 1, 1} vertex A at 0th index vertex B at 1st index vertex C at 2nd index vertex D at 3rd index vertex E at 4th index vertex F at 5th inde In the given graph, each colour represents their own disjoint set,and as we know initially all the nodes are a disjoint set in their own,hence all vertices are uniquely coloured.
Edge1:
We are currently at edge (D, E) with weight = 1 being the smallest amongst
all.
First check if inclusion of this
edge creates any cycle or not.
D & E
are in different set therefore, no cycle will be formed if we include this
edge, therefore we can include this edge.
Parent = {0, 1, 2, 4, 4, 5} Size = {1, 1, 1, 1, 2, 1} parent [D] = E Size [E] = Size [E] + Size [D]
Edge2:
We are currently at edge (F, E) with weight = 2
First check if inclusion of this edge creates any cycle or not.
F & E are in different set therefore, no cycle will be formed if we include this edge, therefore we can include this edge and perform union operation on the two disjoint sets having F and E.
Parent = {0, 1, 2, 4, 4, 4} Size = {1, 1, 1, 1, 3, 1} parent [F] = E Size [E] = Size [E] + Size [F]
Edge3:
We are currently at edge (A, F) with weight = 3
First check if inclusion of this edge creates any cycle or not.
F & A are in different set therefore, no cycle will be formed if we
include this edge, therefore we can include this edge and perform union
operation on the two disjoint sets having A and F.
Now, for combining disjoint sets of A and F, we need to make parent of A
equal to F, but here we see, F is not the parent of its own set, this implies
that parent of A will not be F, instead parent of A will be the parent of F.
Parent = {4, 1, 2, 4, 4, 4} Size = {1, 1, 1, 1, 4, 1} parent [A] = parent [F] = E Size [E] = Size [E] + Size [A]
Edge4:
We are currently at edge (F, B) with weight = 4
First check if inclusion of this edge creates any cycle or not.
F & B are in different set therefore, no cycle will be formed if we
include this edge, therefore we can include this edge and perform union
operation on the two disjoint sets having A and F.
Now, for combining disjoint sets of B and F, we will make parent of F as
parent of B and not F directly.
Parent = {4, 4, 2, 4, 4, 4} Size = {1, 1, 1, 1, 5, 1} parent [B] = parent [F] = E Size [E] = Size [E] + Size [B]
Edge5:
We are currently at edge (B, E)
with weight = 5.
But, inclusion of
this edge creates a cycle as B and E are in same set because parent [B] =
Parent [E] = E, and adding a direct edge between B and E will form a cycle in
the MST being constructed.
Therefore, we
skip this edge.
For edge (A, B)
, this edge will also create a cycle, with the reason being the same, A and B
are in the same disjoint set, with the parent of their set equal to E and
adding a direct edge between A and B will form a cycle in the MST being
constructed.
Therefore, we skip this edge
also.
For edge (A, E)
, this edge will also create a cycle, with the reason being the same, A and E
are in the same disjoint set, with the parent of their set equal to E and
adding a direct edge between A and E will form a cycle in the MST being
constructed.
Therefore, we skip this edge
also.
Now, for edge (C, E)
with weight = 8,
First check if
inclusion of this edge creates any cycle or not.
C & E are in different set therefore, no cycle will be formed if we
include this edge, therefore we can include this edge and perform union
operation on the two disjoint sets having C and E.
Now, for combining disjoint sets of C and E, we will make E as parent of B.
Parent = {4, 4, 4, 4, 4, 4} Size = {1, 1, 1, 1, 6, 1} parent [C] = E Size [E] = Size [E] + Size [C]
Now, we have included a total of 5 edges in minimum spanning tree which is
equal the minimum number of edges required to connect all the vertices and
parent of all the vertices will be a common vertex now.
Therefore we terminate our algorithm here.
Finally, this is Minimum Spanning Tree obtained after applying Kruskal’s Algorithm.
Time Complexity :
Sorting of edges = E log E
now, for (V – 1) times, we performed, union operation and checked for cycle,
this may seem like an O(1)
operation , but this consisted of finding the parents of both the
vertices on any edge whose time complexity is O(Log V)
.
And as we know potential number of edges in any graph can be upto V^2.
Therefore Overall time Complexity for Kruskal’s Algorithm is O(E log E)
package Graphs; import java.util.Arrays; import java.util.Scanner; public class kruskals { public static class edge implements Comparable<edge> { int u; int v; int weight; public edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; } public String toString() { return this.u + " " + this.v + " " + this.weight; } // sorting of the edges will be done on the basis of weights. @Override public int compareTo(edge o) { return this.weight  o.weight; } } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int nodes = scn.nextInt(); int[][] graph = new int[nodes + 1][nodes + 1]; int numEdges = scn.nextInt(); edge[] edges = new edge[numEdges]; for (int edge = 0; edge < numEdges; edge++) { int u = scn.nextInt(), v = scn.nextInt(), w = scn.nextInt(); /* * as the graph will be bidirectional then 'v' will be * neighbour of 'u' and viceversa */ graph[u][v] = graph[v][u] = w; /* add the edge in the edges array which will be * sorted later */ edges[edge] = new edge(u, v, w); } kruskalsAlgo(nodes, numEdges, edges, graph); } public static void kruskalsAlgo(int numVertices, int numEdges, edge[] edges, int[][] graph) { /* for storing minimum spanning tree formed */ int[][] mst = new int[graph.length][graph.length]; /* sort the edges on the basis of their weights * in an increasing order */ Arrays.sort(edges); /* we use parents & size array for creating disjoint sets */ int[] parents = new int[numVertices + 1]; int[] size = new int[numVertices + 1]; for (int vertex = 1; vertex < graph.length; vertex++) { /* * initially all the vertices are a set in * themselves, hence, they are the parent of their * own set, and the size of their set is also one */ parents[vertex] = vertex; size[vertex] = 1; } int edgeCounter = 0; int edgedTaken = 1; /* for connecting all the vertices we need to have * atleast vertices1 edges */ while (edgedTaken <= numVertices  1) { edge e = edges[edgeCounter]; edgeCounter++; /* * we will include only those edges which does * not create any cycle in the constructed minimum * spanning tree */ if (isCyclic(e.u, e.v, parents)) continue; /* * for combining the edge into the MST, we first * need to find the parents of both the vertices, * and then the put combine the smaller set with * larger set */ union(findParent(e.u, parents), findParent(e.v, parents), parents, size); mst[e.u][e.v] = e.weight; edgedTaken++; } /* tree display */ for (int u = 1; u < mst.length; u++) { for (int v = 0; v < mst.length; v++) { if (mst[u][v] != 0) { System.out.println(u + " " + v + " " + mst[u][v]); } } } } public static boolean isCyclic(int u, int v, int[] parents) { /* if the parents of both the vertices of the * edge are same, this means they are connected * to a common vertex, and hence if we put this * edge in the MST then it will create a cycle. */ return findParent(u, parents) == findParent(v, parents); } public static void union(int u, int v, int[] parents, int[] size) { /*find the parent of both the vertices in the current * edge, and merge the larger disjoint set with smaller * disjoint set*/ u = findParent(u, parents); v = findParent(v, parents); if (size[u] > size[v]) { parents[v] = u; size[u] += size[v]; } else { parents[u] = v; size[v] += size[u]; } } public static int findParent(int u, int[] parents) { /*if the parent of any vertex is the vertex itself, * then this is the parent of the the vertex of the * current edge being processed*/ if (parents[u] == u) { return u; } else { /*path compression*/ parents[u] = findParent(parents[u], parents); return parents[u]; } } }
That’s all about Kruskal’s algorithm for finding minimum spanning tree.