Kruskal’s Algorithm

The majority of the algorithms of interest work with data. In the creation and study of algorithms, there are particular data organisation layouts that are crucial. Data structures are essentially means of organising data, to put it another way.

There are two sorts of data structures: linear and nonlinear. Linear data structures include linked lists and arrays. Nonlinear data structures include things like trees and graphs.

Algorithms are techniques for solving issues. In this blog, we’ll look at the Kruskal’s algorithm. Let us define a few words before we begin with the Kruskal’s algorithm:-

1. Graphs: A graph is a nonlinear data structure that consists of nodes and edges. The edges are lines or arcs that link any two nodes in the graph, and the nodes are also known as vertices.

2. Trees: Trees are nonlinear data structures with a graph-like structure. The major distinction between a tree and a graph is that trees only have one path connecting two vertices. Between two vertices, there can only be one path.

3. Minimum Spanning Tree: A Minimum Spanning Tree is a subset of edges in a graph that connects every vertex and minimises the total of the edges. The weight of the spanning tree is equal to the total of the weights assigned to its edges.

Let us now turn our attention to the primary point of discussion, Kruskal’s Algorithm. It’s used to discover the shortest path between two points in a connected weighted graph. The algorithm’s main goal is to locate a subset of edges that may be used to visit every vertex of the graph. Instead of focusing on a global optimum, it uses a greedy method to discover an optimal solution at each stage.

The algorithm:

STEP 1:Create a forest F in such a way that every vertex of the graph is a separate tree.

STEP 2: Create a set E that contains all the edges of the graph.

STEP 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning

STEP 4: Remove an edge from E with minimum weight

STEP 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F

(for combining two trees into one tree).

ELSE

Discard the edge

STEP 6: END

Let’s have a look at an example:

STEP 1: Start with a weighted graph.

STEP 2: Choose the edge with the least weight, if there are more than 1, choose anyone.

STEP 3: Choose the next shortest edge and add it.

STEP 4: Choose the next shortest edge that doesn’t create a cycle and add it.

STEP 5: Choose the next shortest edge that doesn’t create a cycle and add it.

STEP 6: Repeat until you have a spanning tree.

I hope you have a better grasp of Kruskal’s Algorithm as a result of this article.