Kruskal’s Algorithm is a popular algorithm in graph theory used to find the minimum spanning tree (MST) of a connected, weighted graph. It was developed by Joseph Kruskal in 1956 and is one of the most commonly used algorithms in computer science.

In this article, we will discuss Kruskal’s Algorithm in detail, its working, and how to implement it using Python.

Table of Contents

1. What is a Minimum Spanning Tree?
2. Kruskal’s Algorithm Overview
3. Working of Kruskal’s Algorithm
4. Implementing Kruskal’s Algorithm in Python
5. Conclusion
6. FAQs

1. What is a Minimum Spanning Tree?

A minimum spanning tree (MST) is a tree that spans all the vertices of a connected, weighted graph while minimizing the sum of the edge weights. In other words, it is a tree that connects all the vertices of a graph with the minimum possible total edge weight.

2. Kruskal’s Algorithm Overview

Kruskal’s Algorithm is a greedy algorithm that finds the minimum spanning tree of a graph. The algorithm operates by sorting the edges of the graph by weight, and then adding the edges to the MST one by one, in increasing order of weight, as long as the addition of the edge does not create a cycle in the MST.

3. Working of Kruskal’s Algorithm

The following steps are involved in Kruskal’s Algorithm:

1. Sort the edges of the graph by weight.
2. Create a new set for each vertex.
3. Iterate over the sorted edges and add the edge to the MST if it connects two different sets. If the edge connects two vertices in the same set, then it is discarded to avoid creating a cycle.
4. Repeat step 3 until all the vertices are connected in the MST.

4. Implementing Kruskal’s Algorithm in Python

To implement Kruskal’s Algorithm in Python, we need to follow the steps outlined in the previous section. The following code demonstrates how to implement Kruskal’s Algorithm in Python

# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
 
    # Function to add an edge to the graph
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])
 
    # Function to find the parent of a vertex
    def find_parent(self, parent, i):
        if parent[i] == i:
            return i
        return self.find_parent(parent, parent[i])
 
    # Function to merge two sets using rank
    def union(self, parent, rank, x, y):
        xroot = self.find_parent(parent, x)
        yroot = self.find_parent(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
 
    # Function to find the minimum spanning tree
    def kruskal_mst(self):
        result = []
        i = 0
        e = 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(parent, u)
            y = self.find_parent(parent, v)
 
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)
 
        print("Edges in the MST:")
        for u, v, weight in result:
            print("%d - %d: %d" % (u, v, weight)))

The above code creates a Graph class that has a kruskal_mst method that implements Kruskal’s Algorithm. The find_parent and union methods are used to find and merge the sets to which the vertices belong. The add_edge method is used to add edges to the graph.

To use the Graph class to find the MST of a graph, we need to create a Graph object and add the edges to the graph using the add_edge method. Then we can call the kruskal_mst method to find the MST.

Here’s an example of how to use the Graph class:

g = Graph(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.kruskal_mst()

Output:

Edges in the MST:
2 - 3: 4
0 - 3: 5
0 - 1: 10

5. Conclusion

Kruskal’s Algorithm is a popular algorithm used to find the minimum spanning tree of a graph. It is a greedy algorithm that works by adding edges to the MST in increasing order of weight, as long as the addition of the edge does not create a cycle in the MST. In this article, we discussed the working of Kruskal’s Algorithm and demonstrated how to implement it in Python.

6. FAQs

1. What is a minimum spanning tree?
   • A minimum spanning tree is a tree that spans all the vertices of a connected, weighted graph while minimizing the sum of the edge weights.
2. What is Kruskal’s Algorithm?
   • Kruskal’s Algorithm is a popular algorithm in graph theory used to find the minimum spanning tree of a connected, weighted graph.
3. What is a greedy algorithm?
   • A greedy algorithm is an algorithm that makes locally optimal choices at each step with the hope of finding a global optimum.
4. What is the time complexity of Kruskal’s Algorithm?
   • The time complexity of Kruskal’s Algorithm is O(E log E), where E is the number of edges in the graph.
5. Can Kruskal’s Algorithm be used to find the maximum spanning tree of a graph?
   • No, Kruskal’s Algorithm can only be used to find the minimum spanning tree of a graph.

For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear