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.

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
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)
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.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