Question 90 : Explain Kruskal’s algorithm for finding minimum spanning tree

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

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

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]

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]

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]

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]

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]

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 vice-versa
             */
            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 vertices-1 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.