Kruskal’s Algorithm for finding Minimum Spanning Tree

Previous
Next

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 vertices-1 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 = vertices-1


Algorithm

Kruskal’s is a greedy approach which emphasizes on the fact that we must include only those (vertices-1) 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.

  1.  We keep a list of all the edges sorted in an increasing order according to their weights.
  2.  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.
  3.  We need to repeat the same process again until we have (Vertices-1) 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 the same 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 in two 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 the Minimum 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

Kruskals1
Consider this graph,
To find the Minimum Spanning tree of this given bidirectional graph, we first need to sort all the edges in a non-decreasing 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 index

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.


Edge-1:

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]

Kruskal2

Edge-2:

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]

Kruskals3


Edge-3:

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]

Kruskals4


Edge-4:

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]

Kruskal5


Edge-5:

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]

Kruskals6

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.

Kruskals7

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).

That’s all about Kruskal’s algorithm for finding minimum spanning tree.

Latest posts by Ayush Kumar (see all)

Previous
Next

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog