Kruskal’s algorithm

Kruskal’s algorithm is a greedy algorithm which finds the minimum spanning forest in an undirected edge-weighted graph.

First we need to know what a graph means:

Finite no. of vertices connected by a set of edges creates a graph G and G can be a graph if and only if G is a tree, a unique path connects 2 vertices of G, any edge in G is a bridge and G is connected.

Now we need to understand what is a minimum spanning tree:

Suppose we have a weighted graph G, its minimum-cost spanning tree or forest will be tree which has minimum sum of all weights in the edges of that supposed tree. A MST must follow some properties which are that it must never form a cycle and all the vertices in the graph should be covered.

It adds the next lowest weighted edge in each step such that no cycle is formed and a minimum spanning forest is created.

The major difference between Kruskal and Prim’s Algo is that in prims we start form a primary vertex and expand from there where as in kruskal’s we add the edge with lowest weight to the tree and this can create multiple intermediate trees (or a forest) before finding the MST.

Undirected weighted graph

The no. of edges in minimum spanning tree will be vertices minus 1(V-1).The way it works is we create a forest(set of trees) ,where each vertex in the graph is a separate tree. We then take an edge with min weight, if the edge connects two different trees then we add it to the forest, combining two trees in one.

In kruskal’s algo, first we sort all the edges form low weight to high. Then we add the edge with the lowest weight if no cycle is formed, continue to add the edge until we reach all the vertices and a minimum spanning tree is created.

the time complexity of kruskal’s algo is O(E logE) or O(V logV) where E is the no. of edges and V is the no. of vertices

Usually we implement disjoint sets with kruskal’s algo. A forset T is created by the disjoint sets, consists only of the vertices of graph G. Kruskal algo’s concept is based on acyclic graph

Mathematical explanation of Kruskal’s Algorithm is:

let a connected graph G=(V,E) with vertices V=(1,2….,n) and weights be w=E->R here E is the list of Edges.

KRUSKAL(G,w;T)

T ← Ø

I =1 to n do Vi ← {i} od;

Put E into a priority queue Q with priority function w;

While Q = Ø do

e:= determine (Q);

Find the end vertices u and v of e;

Find the components Vu and Vv containing u and v , respectively ;

If Vu ≠ Vv then Merge(Vu,Vv); T ←T U{e} fi

od

Pesudocode of Kruskal’s Algorithm:

Procedure kruskal(G)

G- input graph :

begin

A = Ø

For each vertex v E G.V:

MAKE-SET(v)

For each edge (u, v) E G.E ordered by weight in increasing order (u, v):

if FIND-SET(u) + FIND-SET(v): A = A U {(u, v)}

UNION(u, v)

return A

end kruskal;