Kruskal Algorithm- Explained with example!

Already we have discussed two greedy technique algorithms in our previous articles and in this article, we will briefly understand the concept and the implementation of the kruskal algorithm. Like other greedy technique based algorithm, the Kruskal algorithm is also used to find the Minimum Spanning Tree (MST) of the graph. MST is the subset of the edges that connects all the vertices together without forming any loop or cycles and at the possible minimum weight

KRUSKAL ALGORITHM:

Initially, this algorithm finds a least possible weight that connects any two nodes in the graph.

1. Get the number of vertices n, vertices and edges weight.
2. Get the edge weights and place it in the priority queue in ascending order.
3. Create a disjoint set where each vertex will be separate disjoint set.
4. Find the minimum value from the priority queue and its connecting vertices.
5. Make a union of those vertices and mark the edges as accepted if it does not form a cycle in the minimum spanning tree and delete the minimum from the priority queue.
6. Repeat all the steps until all the vertices in the tree are connected.

SOLVING STEPS:

1. List out all the edges from the given graph. Make the note of edge and the weight of the respective node.
2. Sort the edges in ascending order based on the edge weight.

   

3. Pick the smallest edge and check if it forms a cycle with the formed MST.
4. If this edge forms cycle, discard this edge and go to the next edge otherwise include this edge to the minimum spanning tree formed so far.
5. The above-mentioned step is repeated until there are (N-1) edges in the MST. N- no. of vertices.

   

Let us see how to implement this Kruskal’s algorithm in Java programming. If you need to implement this algorithm in any other programming languages let us know in the comment section.

JAVA IMPLEMENTATION OF KRUSKAL ALGORITHM:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class kruskal
{
    class Edge implements Comparable<Edge>
    {
        int src, dest, weight;
        public int compareTo(Edge compareEdge)
        {
            return this.weight-compareEdge.weight;
        }
    };
    class subset
    {
        int parent, rank;
    };
 
    int V, E;    
    Edge edge[];
    kruskal(int v, int e)
    {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i=0; i<e; ++i)
            edge[i] = new Edge();
    }
    int find(subset subsets[], int i)
    {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
 
        return subsets[i].parent;
    }
    void Union(subset subsets[], int x, int y)
    {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else
        {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
  // The main function to construct MST using Kruskal's algorithm
    void KruskalMST()
    {
        Edge result[] = new Edge[V];  
        int e = 0;  
        int i = 0; 
        for (i=0; i<V; ++i)
        Arrays.sort(edge);
        subset subsets[] = new subset[V];
        for(i=0; i<V; ++i)
            subsets[i]=new subset();
        for (int v = 0; v < V; ++v)
        {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
        i = 0; 
        while (e < V - 1)
        {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
            if (x != y)
            {
                result[e++] = next_edge;
                Union(subsets, x, y);
            }
           
        }
 
        System.out.println("Following are the edges in " + 
                                     "the constructed MST");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src+" -- " + 
                   result[i].dest+" == " + result[i].weight);
    }
 
    // Driver Program
    public static void main (String[] args)
    {
 
        /* Let us create following weighted graph
                 10
            0--------1
            |  \     |
           6|   5\   |15
            |      \ |
            2--------3
                4       */
        int V = 4;  
        int E = 5;  
        kruskal graph = new kruskal(V, E);
 
        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;
 
        // add edge 0-2
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;
 
        // add edge 0-3
        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;
 
        // add edge 1-3
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;
 
        // add edge 2-3
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;
 
        graph.KruskalMST();
    }
}

The output of this program will be:

Hope this article will help you to understand the Algorithm. If you are interested in programming do subscribe to our E-mail newsletter for all programming tutorials. Also, check our prim’s and Dijkstra algorithm articles.