Python Pool: 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:

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:

Move: 1

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

Move: 2

Now, we will add the edge 0-1:

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.

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

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

• Understanding Python Bubble Sort with examples
• Top 10 Algorithms for Data Science
• Tower of Hanoi Implementation in Python
• 10 Machine Learning Algorithms for beginners
• Pigeonhole Sort in Python With Algorithm and Code Snippet

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!

The post Kruskal’s algorithm: Implementation in Python appeared first on Python Pool.

from Planet Python
via read more