Kruskal’s Algorithm

How’s the day greedy techs, hope all are safe and fine today in this blog I’m going to explain Kruskal’s algorithm. And we will also see the complexity of working and example of this algorithm.

Now before we go to Kruskal’s algorithm let’s find out what basically is a spanning tree.

SPANNING TREE- A spanning tree is a subgraph or a smaller graph of an undirected connected graph.

MINIMUM SPANNING TREE- minimum spanning tree is a spanning tree whose sum of the edges or its cost is minimum.

Now let's move on to the main topic:

Kruskal’s algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of this algorithm is to traverse every vertex of the graph by finding the subset of the edges.

It follows the greedy approach that finds a superlative solution at every stage instead of focusing on a global prime.

WORKING OF KRUSKAL’S ALGORITHM

Using this algorithm we find MST(MINIMUM SPANNING TREE) by starting from the edges until we make an MST.

STEPS FOR IMPLEMENTING KRUSKAL’S ALGO

1. First of all, we sort the edges from lowest weight to highest weight.
2. Then we take the edge with the lowest weight and add it to the spanning tree. And if the edge creates a loop /cycle then we discard that edge.
3. Now we keep adding the edges according to their weights i.e. lowest to highest. Until an MST is created.

APPLICATIONS OF KRUSKAL’S ALGORITHM

• Kruskal’s algorithm can be used to layout electrical wiring among cities.
• It can be used to lay down LAN connections.

EXAMPLE OF KRUSKAL’S ALGORITHM

Now we will understand Kruskal’s algorithm by an example, it will be easy to understand with the help of this example.

Suppose this is a weighted graph and we have to create an MST of this graph.

Now according to our steps, we choose the edge with the least weight so we have chosen the edge with the weight 2. because it has the lowest weight. since there is more than one edge with the same weight so no problem we can choose any one of them.

Now in the next step we have to choose the next shorter edge so here the next shorter edge is 2 so we will add it to the spanning tree.

Similarly again we will find the next shorter edge and see that it doesn’t create any cycle and will add to the Spanning tree.

We have to repeat these steps until we get a MINIMUM SPANNING TREE.

Pseudo code of Kruskal’s algorithm

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

This pseudo-code uses a union-find algorithm which divides the vertices into clusters and helps us to check whether the vertices are in the same cluster or not. And hence decide whether they create a cycle or not

Kruskal’s Algorithm Complexity

The time complexity Of Kruskal’s Algorithm is: O(E log E).