Kruskal’s Algorithm

Kruskal’s algorithm is a minimum spanning tree  algorithm that takes a graph as input and finds the subset of the edges of that graph which

• form a tree that includes every vertex
• has the minimum sum of weights among all the trees that can be formed from the graph

How Kruskal’s algorithm works

It falls under a class of algorithms called Greedy Algorithm that find the local optimum in the hopes of finding a global optimum.

We start from the edges with the lowest weight and keep adding edges until we reach our goal.

The steps for implementing Kruskal’s algorithm are as follows:

1. Sort all the edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Example of Kruskal’s algorithm

Start with a weighted graphChoose the edge with the least weight, if there are more than 1, choose anyoneChoose the next shortest edge and add itChoose the next shortest edge that doesn’t create a cycle and add itChoose the next shortest edge that doesn’t create a cycle and add itRepeat until you have a spanning tree

Kruskal Algorithm Pseudocode

Any minimum spanning tree algorithm revolves around checking if adding an edge creates a loop or not.

The most common way to find this out is an algorithm called Union find . The Union-Find algorithm divides the vertices into clusters and allows us to check if two vertices belong to the same cluster or not and hence decide whether adding an edge creates a cycle.

KRUSKAL(G):

A = ∅

For each vertex v ∈ G.V:

    MAKE-SET(v)

For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):

    if FIND-SET(u) ≠ FIND-SET(v):       

    A = A ∪ {(u, v)}

    UNION(u, v)

return A

Python Examples

# Kruskal’s algorithm in Python

class Graph:

    def __init__(self, vertices):

        self.V = vertices

        self.graph = []

    def add_edge(self, u, v, w):

        self.graph.append([u, v, w])

    # Search function

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

    def apply_union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

        else:

            parent[yroot] = xroot

            rank[xroot] += 1

    #  Applying Kruskal algorithm

    def kruskal_algo(self):

        result = []

        i, e = 0, 0

        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = []

        rank = []

        for node in range(self.V):

            parent.append(node)

            rank.append(0)

        while e < self.V – 1:

            u, v, w = self.graph[i]

            i = i + 1

            x = self.find(parent, u)

            y = self.find(parent, v)

            if x != y:

                e = e + 1

                result.append([u, v, w])

                self.apply_union(parent, rank, x, y)

        for u, v, weight in result:

            print(“%d – %d: %d” % (u, v, weight))

g = Graph(6)

g.add_edge(0, 1, 4)

g.add_edge(0, 2, 4)

g.add_edge(1, 2, 2)

g.add_edge(1, 0, 4)

g.add_edge(2, 0, 4)

g.add_edge(2, 1, 2)

g.add_edge(2, 3, 3)

g.add_edge(2, 5, 2)

g.add_edge(2, 4, 4)

g.add_edge(3, 2, 3)

g.add_edge(3, 4, 3)

g.add_edge(4, 2, 4)

g.add_edge(4, 3, 3)

g.add_edge(5, 2, 2)

g.add_edge(5, 4, 3)

g.kruskal_algo()

Kruskal’s vs Prim’s Algorithm

Prim’s algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the MST of a graph. Instead of starting from an edge, Prim’s algorithm starts from a vertex and keeps adding lowest-weight edges which aren’t in the tree, until all vertices have been covered.