Python Program to Implementation of Kruskal’s Algorithm

Kruskal’s Algorithm is a popular algorithm used to find the minimum spanning tree in a graph. The algorithm does not depend on the starting point of the graph and works with a disconnected graph as well. In this article, we’ll be implementing Kruskal’s Algorithm in Python and walking through each step.

Minimum Spanning Tree

A minimum spanning tree(MST) of a weighted, undirected graph is a subgraph that connects all vertices in the graph with the minimum possible total edge weight. A spanning tree is a tree that includes all of the vertices in the graph, exactly once. As the name suggests, minimum spanning trees are spanning trees where the total weight of all edges in the tree is minimized.

Kruskal’s Algorithm

Kruskal’s Algorithm is a greedy algorithm that works by starting with the smallest edge and building the minimum spanning tree from there. The Kruskal’s Algorithm algorithm finds the minimum spanning tree by iterating over all the edges in the graph and picking the edge that connects two different disjoint groups of vertices with the smallest weight. The process then continues until all the vertices are connected.

The Kruskal’s Algorithm algorithm can be implemented using a union-find algorithm. In this algorithm, we perform a union between the two disjoint sets of vertices represented by the root node of each set or group, and we keep doing it until we have only one group of vertices left.

Implementation of Kruskal’s Algorithm in Python

We will now implement Kruskal’s Algorithm in Python. We will start by creating a Weighted Directed Graph. We will also add various helper functions to help in implementing the algorithm. The full implementation of this algorithm is provided below:

class WeightedDirectedGraph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

        #function to add edges to the graph
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

        #function to find set of an element i
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

        #function that does union of two sets x and y
        # uses union by rank
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        # Attach smaller rank tree under root of high rank tree
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot

        # If ranks are same, then make one as root and increment its rank by one
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

        # The main function to construct MST using Kruskal's algorithm
    def kruskals_algorithm(self):
        result = []  # This will store the resultant MST

        i = 0  # An index variable, used for sorted edges
        e = 0  # An index variable, used for result[]

        # Sort all the edges in non-decreasing order of their weight.
        # If we are not allowed to change the given graph, we can create copy of graph
        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = []
        rank = []

        # Create V subsets with single elements
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        # Number of edges to be taken is equal to V-1
        while e < self.V - 1:

            # Step 2: Pick the smallest edge and increment the index for next iteration
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            # If including this edge does't cause cycle, include it
            # in result and increment the index of result for next vertex
            if x != y:
                result.append([u, v, w])
                e = e + 1
                self.union(parent, rank, x, y)

        return result

The implementation of Kruskal’s Algorithm in Python can be divided into the following steps:

1. Define the number of vertices and create an empty list of the graph.
2. Add edges to the graph using the add_edge() function.
3. Define the find() function for performing union-find operations.
4. Define the union() function that creates the different sets and traverses the graph to find the minimum spanning tree.
5. The kruskals_algorithm() function executes the Kruskal’s Algorithm and returns a list of edges that make up the minimum spanning tree.

Example

Let’s go through a quick example to see how Kruskal’s Algorithm works.

To find the minimum spanning tree of this graph, we will execute the following code:

g = WeightedDirectedGraph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.kruskals_algorithm()

The above code creates a graph with four vertices and five edges. We add the edges to the graph using the add_edge() function. We then call the kruskals_algorithm() function on this graph to find the minimum spanning tree.

The output of the above code will be:

[[2, 3, 4], [0, 3, 5], [0, 1, 10]]

Conclusion

In this article, we have explored Kruskal’s Algorithm to find the minimum spanning tree in a graph. We also implemented the algorithm in Python by first creating a Weighted Directed Graph and then adding various helper functions. We then executed a sample code to find the minimum spanning tree of the given graph. Kruskal’s Algorithm is an efficient and popular algorithm that can be used to find the minimum spanning tree in a graph with a time-complexity of O(E log E), where E is the number of edges in the graph.