Kruskal algorithm

Kruskal algorithm is used to find the shortest path between two points in a connected weighted graph. This algorithm comes under greedy technique. This algorithm used to find the minimum cost of spanning tree. It converts the given graph into spanning tree considering each node as a separate tree. While making spanning tree, the number of vertex in the graph should be same in tree. The edge of spanning tree should be one less than the vertex of graph. While making tree, we must choose the minimum weight of edge first and keeps adding nodes to the tree only if the chosen edge does not form any cycle. It makes a locally optimal choice, intending to find global solution. To find the cost of tree we need to add the weights of edge. We will find that graph is not cyclic and the edges are one less than vertex. Time complexity of Kruskal algorithm is O(ElogV), where V being the vertex.

Steps to Kruskal Algorithm:

· First we arrange all the edges in increasing order by comparing their edge weight.

· Pick the smallest edge, while doing the process we have to keep in mind to not to make loop in the spanning tree.

· If the edge make loop then discard it otherwise add it in the MST.

· The Spanning Tree can be discontinues in the initial steps or may look like multiple spanning trees.

· Repeat the steps until it has |n-1| edges, where n is the total number of nodes in the Spanning Tree.

Here is the step wise process to find Kruskal algorithm:

A MST algorithm checks that while adding the edges a loop is created or not. Union Find is the common way to find this out. It divides the vertices into clusters and check whether two vertices belong to the same cluster or not and decide whether it create a cycle while adding the edges.

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