Kruskal’s algorithm: Implementation in Python

Hello coders!! In this article, we will be digging into Kruskal’s Algorithm and learn how to implement it in Python. Let us first understand what does it mean. This algorithm is used to create a minimum spanning tree from a weighted graph. Now, we will look into this topic in detail.

Kruskal’s algorithm for minimum spanning tree:

Kruskal’s Algorithm is implemented to create an MST from an undirected, weighted, and connected graph. The edges are sorted in ascending order of weights and added one by one till all the vertices are included in it. It is a Greedy Algorithm as the edges are chosen in increasing order of weights. No cycle is created in this algorithm.

  1. At first, we will sort the edges in ascending order of their weights.
  2. After this, select the edge having the minimum weight and add it to the MST. If an edge creates a cycle, we reject it.
  3. Repeat the above steps till we cover all the vertices.

Illustration of Kruskal’s Algorithm:

Let us take the following graph as an example:

Consider this graph for illustration kruskal's algorithm python
Move: 0

Now, the edges in ascending order of their weights are:

  • 0-2 : 5
  • 3-4 : 7
  • 0-1 : 8
  • 1-2 : 9
  • 2-4 : 10
  • 1-3 : 11

Now, we will select the minimum weighted edge, i.e. 0-2, and add it to MST:

edge 0-2 is added in kruskal's algorithm python
Move: 1

The next edge that we will add to our MST is edge 3-4:

edge 3-4 is added
Move: 2

Now, we will add the edge 0-1:

edge 1-0 is added
Move: 3

Now, we have the edge 1-2 next, however, we we add this edge then a cycle will be created. As a result, this edge will be rejected.

After adding the edge 2-4, the MST is complete, as all the vertices are now included.

Final MST
Minimum Spanning Tree

Implementation of Kruskal’s Algorithm in Python:

class Graph:
    def __init__(self, vertex):
        self.V = vertex
        self.graph = []

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


    def search(self, parent, i):
        if parent[i] == i:
            return i
        return self.search(parent, parent[i])

    def apply_union(self, parent, rank, x, y):
        xroot = self.search(parent, x)
        yroot = self.search(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

 
    def kruskal(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.search(parent, u)
            y = self.search(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("Edge:",u, v,end =" ")
            print("-",weight)


g = Graph(5)
g.add_edge(0, 1, 8)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 9)
g.add_edge(1, 3, 11)
g.add_edge(2, 3, 15)
g.add_edge(2, 4, 10)
g.add_edge(3, 4, 7)
g.kruskal()

Output:

output of  kruskal's algorithm python
Output

Time complexity:

The time complexity Of Kruskal’s Algorithm is: O(E log V)

Advantages of Kruskal’s Algorithm:

  • It is easy to implement
  • It offers a good control over the resulting MST

Application of Kruskal’s Algorithm:

  • Used to make electrical wiring layout
  • Used to make LAN connection
  • A network of pipes for drinking water or natural gas.
  • Single-link Cluster.

Must Read

Conclusion:

This is all about Kruskal’s algorithm. We learned the algorithm in detail and also its implementation in python. WE also saw its advantages and its different applications in day to day needs.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

Subscribe
Notify of
guest
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Umer Arshad
Umer Arshad
19 days ago

very good work..
it helped us alot in making our assignment