Kruskal's Minimum Spanning Tree Algorithm

  • Kruskal’s algorithm creates a minimum spanning tree from a weighted undirected graph by adding edges in increasing order of weights.
  • Kruskal’s algorithm is greedy in nature as the edges are chosen in the increasing order of their weights.
  • The algorithm makes sure that the addition of new edges to the spanning tree does not create a cycle within it.
  • A union-by-rank & path compression technique used for merging two disjoint subsets could be used to efficiently add edges to the minimum spanning tree.

Algorithm : Kruskal’s minimum spanning tree ( Graph G )

0.    Create an empty minimum spanning tree M i.e M = ∅ (zero edges)
1.     Sort the edge-list of the graph G in ascending order of weights.
2.    For each edge ( A, B ) in the sorted edge-list.
3.         If Find_Set_Of_A != Find_Set_Of_B, then
4.              Add edge A-B to the minimum spanning tree M i.e M = M + edge ( A - B )
5.              Make a set / union of Find_Set_Of_A + Find_Set_Of_B.

Example of finding the minimum spanning tree using Kruskal’s algorithm Kruskals_MST

Time complexity of Kruskal’s algorithm : O ( E log ( E ) ) or O ( E log ( V )). Where E is the number of edges and V is the number of vertices.

Why is the time complexity of Kruskal's algorithm O ( E log ( E ) ) or O ( E log ( V ) ) ?

Kruskal’s minimum spanning tree implementation 

from typing import List # for annotations

class Edge :

   def __init__(self, arg_src : int, arg_dst : int, arg_weight : int) :
       self.src = arg_src
       self.dst = arg_dst
       self.weight = arg_weight

class Graph :

    def __init__(self, num_nodes : int, edgelist : List[Edge]) :
        self.num_nodes = num_nodes
        self.edgelist  = edgelist
        self.parent    = []
        self.rank      = []
        # mst stores edges of the minimum spanning tree
        self.mst       = []

    def FindParent (self, node : int) :
        # With path-compression.
        if node != self.parent[node] :
            self.parent[node] = self.FindParent(self.parent[node])
        return self.parent[node]

        # Without path compression
        # if node == self.parent[node] :
        #    return node
        # return self.FindParent(self.parent[node])

    def KruskalMST (self) :

        # Sort objects of an Edge class based on attribute (weight)
        self.edgelist.sort(key = lambda Edge : Edge.weight)

        self.parent = [None] * self.num_nodes
        self.rank   = [None] * self.num_nodes

        for n in range(self.num_nodes) :
            self.parent[n] = n # Every node is the parent of itself at the beginning
            self.rank[n] = 0   # Rank of every node is 0 at the beginning

        for edge in self.edgelist :
            root1 = self.FindParent(edge.src)
            root2 = self.FindParent(edge.dst)

            # Parents of the source and destination nodes are not in the same subset
            # Add the edge to the spanning tree
            if root1 != root2 :
               self.mst.append(edge)
               if self.rank[root1] < self.rank[root2] :
                  self.parent[root1] = root2
                  self.rank[root2] += 1
               else :
                  self.parent[root2] = root1
                  self.rank[root1] += 1

        print("\nEdges of minimum spanning tree in graph :", end=' ')
        cost = 0
        for edge in self.mst :
            print("[" + str(edge.src) + "-" + str(edge.dst) + "](" + str(edge.weight) + ")", end = ' ')
            cost += edge.weight
        print("\nCost of minimum spanning tree : " +str(cost))

def main() :

    # Edge(source, destination, weight)
    num_nodes = 6
    e1 = Edge(0, 1, 4)
    e2 = Edge(0, 2, 1)
    e3 = Edge(0, 3, 5)
    e4 = Edge(1, 3, 2)
    e5 = Edge(1, 4, 3)
    e6 = Edge(1, 5, 3)
    e7 = Edge(2, 3, 2)
    e8 = Edge(2, 4, 8)
    e9 = Edge(3, 4, 1)
    e10 = Edge(4, 5, 3)

    g1 = Graph(num_nodes, [e1, e2, e3, e4, e5, e6, e7, e8, e9, e10])
    g1.KruskalMST()

    num_nodes = 7
    a = Edge(0, 1, 1)
    b = Edge(0, 2, 2)
    c = Edge(0, 3, 1)
    d = Edge(0, 4, 1)
    e = Edge(0, 5, 2)
    f = Edge(0, 6, 1)
    g = Edge(1, 2, 2)
    h = Edge(1, 6, 2)
    i = Edge(2, 3, 1)
    j = Edge(3, 4, 2)
    k = Edge(4, 5, 2)
    l = Edge(5, 6, 1)

    g2 = Graph(num_nodes, [a, b, c, d, e, f, g, h, i, j, k, l])
    g2.KruskalMST()

if __name__ == "__main__" :
    main()

Output

Edges of minimum spanning tree in graph : [0-2](1) [3-4](1) [1-3](2) [2-3](2) [1-5](3) 
Cost of minimum spanning tree : 9

Edges of minimum spanning tree in graph : [0-1](1) [0-3](1) [0-4](1) [0-6](1) [2-3](1) [5-6](1) 
Cost of minimum spanning tree : 6

#include<iostream>
#include<vector>
#include<algorithm>

class Edge {

    public:

    int node_start;
    int node_end;
    int weight;
    Edge(){}
    Edge(int node1, int node2, int wt): node_start(node1), node_end(node2), weight(wt){}
};

bool CompareCost (const Edge a, const Edge b) {
     return a.weight < b.weight;
}

class Graph{

    private:
    int num_nodes;
    std :: vector<Edge> edgelist; // edgelist will store the edges of minimum spanning tree
    std :: vector<int> parent;
    std :: vector<int> rank;

    public:
    Graph(){}
    Graph (int num_nodes)
    {
        this->num_nodes = num_nodes;
        parent.resize(num_nodes);
        rank.resize(num_nodes);
    }

    void AddEdge(Edge e);
    int FindParent(int node);
    void KruskalMST(std :: vector<Edge>&);
    void DisplayEdges(std :: vector<Edge>&);
};

void Graph :: AddEdge (Edge e) {
    edgelist.push_back(e);
}

int Graph :: FindParent (int node) {

    // With path compression
    if ( node != parent[node] )
        parent[node] = FindParent(parent[node]);
     return parent[node];

    /* Without path compression
    if ( node == parent[node] )
        return node;
     return FindParent(parent[node]); */
}

void Graph :: DisplayEdges (std :: vector<Edge>& mst) {

    int cost = 0;
    std :: cout << "Edges of minimum spanning tree : ";
    for (auto& e : mst) {
        std :: cout << "[" << e.node_start << "-" << e.node_end << "](" << e.weight << ") ";
        cost += e.weight;
    }
    std :: cout << "\nCost of minimum spanning tree : " << cost << std :: endl;
}

//Funtion implements Kruskal's algorithm and finds the minimum spanning tree.
void Graph :: KruskalMST (std :: vector<Edge>& result) {

    for (int i=0; i<num_nodes; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // Sort the edges based on their weights
    sort(edgelist.begin(), edgelist.end(), CompareCost);

    // Apply union-by-rank technique to find the minimum spanning tree.
    for (auto& e : edgelist) {
        int root1 = FindParent(e.node_start);
        int root2 = FindParent(e.node_end);

        if (root1 != root2) {
           result.push_back(e);
           if (rank[root1] < rank[root2]) {
              parent[root1] = root2;
              rank[root2]++;
           } else {
              parent[root2] = root1;
              rank[root1]++;
           }
        }
    }
}

int main() {

    int num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

    Edge e1(0, 1, 4);
    Edge e2(0, 2, 1);
    Edge e3(0, 3, 5);
    Edge e4(1, 3, 2);
    Edge e5(1, 4, 3);
    Edge e6(1, 5, 3);
    Edge e7(2, 3, 2);
    Edge e8(2, 4, 8);
    Edge e9(3, 4, 1);
    Edge e10(4, 5, 3);

    Graph g1(num_nodes);
    g1.AddEdge(e1);
    g1.AddEdge(e2);
    g1.AddEdge(e3);
    g1.AddEdge(e4);
    g1.AddEdge(e5);
    g1.AddEdge(e6);
    g1.AddEdge(e7);
    g1.AddEdge(e8);
    g1.AddEdge(e9);
    g1.AddEdge(e10);

    std :: vector<Edge> mst; // mst will contain the minimum spanning tree
    g1.KruskalMST(mst);
    g1.DisplayEdges(mst);

    num_nodes = 7;

    Edge a(0, 1, 1);
    Edge b(0, 2, 2);
    Edge c(0, 3, 1);
    Edge d(0, 4, 1);
    Edge e(0, 5, 2);
    Edge f(0, 6, 1);
    Edge g(1, 2, 2);
    Edge h(1, 6, 2);
    Edge i(2, 3, 1);
    Edge j(3, 4, 2);
    Edge k(4, 5, 2);
    Edge l(5, 6, 1);

    Graph g2(num_nodes);
    g2.AddEdge(a);
    g2.AddEdge(b);
    g2.AddEdge(c);
    g2.AddEdge(d);
    g2.AddEdge(e);
    g2.AddEdge(f);
    g2.AddEdge(g);
    g2.AddEdge(h);
    g2.AddEdge(i);
    g2.AddEdge(j);
    g2.AddEdge(k);
    g2.AddEdge(l);

    mst.clear();
    g2.KruskalMST(mst);
    g1.DisplayEdges(mst);

    return 0;
}

Output

Edges of minimum spanning tree are : [0-2](1) [3-4](1) [1-3](2) [2-3](2) [1-5](3) 
Cost of minimum spanning tree : 9
Edges of minimum spanning tree : [0-1](1) [0-3](1) [0-4](1) [0-6](1) [2-3](1) [5-6](1) 
Cost of minimum spanning tree : 6

import java.util.ArrayList;
import java.util.List;

class Edge {

    int node_start;
    int node_end;
    int weight;
    Edge (int node1, int node2, int wt) {
        node_start = node1;
        node_end = node2;
        weight = wt;
    }

    public int GetWeight() {
        return weight;
    }
};

class Graph {

    private int num_nodes;
    private List<Edge> edgelist = new ArrayList<Edge>(); // Edgelist stores the edges of MST
    private List<Integer> parent;
    private List<Integer> rank;

    Graph (int num_nodes) {
        this.num_nodes = num_nodes;
        parent = new ArrayList<Integer>(num_nodes);
        rank = new ArrayList<Integer>(num_nodes);
    }

    public void AddEdge (Edge e) {
        edgelist.add(e);
    }

    public int FindParent (int node) {

        // With path compression
        if ( node != parent.get(node) )
            parent.set(node, FindParent(parent.get(node)));

        return parent.get(node);

        /* Without path compression
        if ( node == parent.get(node) )
            return node;

        return FindParent(parent.get(node)); */
    }

    //Funtion implements Kruskal's algorithm and finds the minimum spanning tree.
    public void KruskalMST (List<Edge> result) {

        for (int i=0; i<num_nodes; i++) {
            parent.add(i, i); // Initially set every node as the parent of itself.
            rank.add(i, 0);   // Initial rank of each node is 0.
        }

        // Lambda expression to sort the edges based on their weights
        edgelist.sort((Edge e1, Edge e2)->e1.GetWeight()-e2.GetWeight());

        for (Edge e : edgelist) {

            int root1 = FindParent(e.node_start);
            int root2 = FindParent(e.node_end);
            // Union by rank technique to find minimum spanning tree.
            if (root1 != root2) {
                result.add(e);
                if (rank.get(root1) < rank.get(root2)) {
                   parent.set(root1, root2);
                   rank.set(root2, rank.get(root2) + 1);
                } else {
                   parent.set(root2, root1);
                   rank.set(root1, rank.get(root1) + 1);
                }
            }
        }
    }

    public void DisplayEdges(List<Edge> result) {
        int cost = 0;
        System.out.print( "\nEdges of minimum spanning tree : ");
        for (Edge edge : result) {
            System.out.print( "[" + edge.node_start + "-" + edge.node_end + "]-(" + edge.weight + ") ");
            cost += edge.weight;
        }
        System.out.println("\nCost of minimum spanning tree : " + cost);
    }

    public static void main (String args[]) {

        int num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

        // Edge (source, dest, weight);
        Edge e1 = new Edge(0, 1, 4);
        Edge e2 = new Edge(0, 2, 1);
        Edge e3 = new Edge(0, 3, 5);
        Edge e4 = new Edge(1, 3, 2);
        Edge e5 = new Edge(1, 4, 3);
        Edge e6 = new Edge(1, 5, 3);
        Edge e7 = new Edge(2, 3, 2);
        Edge e8 = new Edge(2, 4, 8);
        Edge e9 = new Edge(3, 4, 1);
        Edge e10 = new Edge(4, 5, 3);

        Graph g1 = new Graph(num_nodes);

        g1.AddEdge(e1);
        g1.AddEdge(e2);
        g1.AddEdge(e3);
        g1.AddEdge(e4);
        g1.AddEdge(e5);
        g1.AddEdge(e6);
        g1.AddEdge(e7);
        g1.AddEdge(e8);
        g1.AddEdge(e9);
        g1.AddEdge(e10);

        List<Edge> mst = new ArrayList<Edge>();
        g1.KruskalMST(mst);
        g1.DisplayEdges(mst);

        num_nodes = 7;

        Edge a = new Edge(0, 1, 1);
        Edge b = new Edge(0, 2, 2);
        Edge c = new Edge(0, 3, 1);
        Edge d = new Edge(0, 4, 1);
        Edge e = new Edge(0, 5, 2);
        Edge f = new Edge(0, 6, 1);
        Edge g = new Edge(1, 2, 2);
        Edge h = new Edge(1, 6, 2);
        Edge i = new Edge(2, 3, 1);
        Edge j = new Edge(3, 4, 2);
        Edge k = new Edge(4, 5, 2);
        Edge l = new Edge(5, 6, 1);

        Graph g2 = new Graph(num_nodes);
        g2.AddEdge(a);
        g2.AddEdge(b);
        g2.AddEdge(c);
        g2.AddEdge(d);
        g2.AddEdge(e);
        g2.AddEdge(f);
        g2.AddEdge(g);
        g2.AddEdge(h);
        g2.AddEdge(i);
        g2.AddEdge(j);
        g2.AddEdge(k);
        g2.AddEdge(l);

        mst.clear();
        g2.KruskalMST(mst);
        g2.DisplayEdges(mst);
    }
}

Output

Edges of minimum spanning tree : [0-2]-(1) [3-4]-(1) [1-3]-(2) [2-3]-(2) [1-5]-(3) 
Cost of minimum spanning tree : 9

Edges of minimum spanning tree : [0-1]-(1) [0-3]-(1) [0-4]-(1) [0-6]-(1) [2-3]-(1) [5-6]-(1) 
Cost of minimum spanning tree : 6

Copyright (c) 2019-2024, Algotree.org.
All rights reserved.