Kruskal Algorithm In Python

Chapter: Python Last Updated: 28-11-2020 18:58:02 UTC

Program:

            /* ............... START ............... */
                
# 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()
                /* ............... END ............... */
        

Output

1 - 2: 2
2 - 5: 2
2 - 3: 3
3 - 4: 3
0 - 1: 4

Notes:

  • 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.
  • A single graph can have many different spanning trees.
  • The steps for implementing Kruskal's algorithm are as follows:
  • 1. First step is to sort 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.
Similar Programs Chapter Last Updated
Python Date Difference In Days Python 01-04-2023
Bellman Ford Algorithm In Python Python 25-03-2023
Python Program To Display Current Date And Time Python 24-03-2023
Binary Search Tree Implementation Python Python 21-03-2023
Python Program To Check Palindrome Number Python 12-03-2023
How to Merge Two PDF Files Using Python Python 12-03-2023
Python Tuples Example Python 19-11-2021
Python Iterator Example Python 12-11-2021
Python Lambda Functions Python 11-11-2021
Integer To String In Python Python 22-10-2021
Python Datetime Format Python 21-10-2021
Range Function In Python | Python range () Python 11-10-2021
Python Desktop Notification Popup In Linux Python 10-07-2021
Python JSON Parser Example | How To Parse JSON In Python Python 25-06-2021
Python PIP | How To Install Packages In Python Python 16-06-2021
How To Access Python Dictionary Python 14-06-2021
Dictionary In Python Examples Python 10-06-2021
Shortest Path Algorithm In Python Python 23-02-2021
Merge Sort In Python Python 01-12-2020
Python Mysql Connector Example Python 21-11-2020
Add To Set Python Python 05-10-2018
Set In Python Python 05-10-2018
List In Python Python 29-09-2018
Integer To String Python Python 29-09-2018
Python Variables Python 21-09-2018
Python String Contains Python 15-09-2018
String In Python Python 22-09-2018
Python Switch Statement Python 20-09-2018
Python Function Example Python 14-09-2018
Python If Statement Python 14-09-2018

1 2