Kruskal's Algorithm implemented in C++ and Python

Kruskal’s minimum spanning tree algorithm

Kruskal’s algorithm creates a minimum spanning tree from a weighted undirected graph by adding edges in ascending order of weights till all the vertices are contained in it. Kruskal’s algorithm gets greedy as it chooses edges in increasing order of weights. The algorithm makes sure that the addition of new edges to the spanning tree does not create a cycle within it.


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.
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(Elog(E)) or O(Elog(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(Elog(E)) or O(Elog(V))?

C++

C++ : Kruskal's minimum spanning tree algorithm implemented in C++14


Python : Kruskal’s minimum spanning tree algorithm implemented in Python 3.7

from dataclasses import dataclass, field

@dataclass
class Edge :
   src : int
   dst : int
   weight : int

@dataclass
class Graph :

    num_nodes : int
    edgelist : list
    parent : list = field(default_factory = list)
    rank : list = field(default_factory = list)

    # mst stores edges of the minimum spanning tree
    mst : list = field(default_factory = list)

    def FindParent(self, node) :

        if self.parent[node] == 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("Edges of minimum spanning tree are in Graph 1 :", 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 of Kruskal’s minimum spanning tree algorithm implemented in Python 3.6

Edges of minimum spanning tree are in Graph 1 : [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 are in Graph 1 : [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-2020, Algotree.org.
All rights reserved.