# Kruskal’s Algorithm

## Introduction to Kruskal’s Algorithm

Kruskal’s Algorithm Problem: Find minimum spanning tree from given weighted, undirected graph G = <V, E, W>

• Joseph Kruskal has suggested a greedy approach to find MST from given weighted, undirected graph.
• The algorithm first sorts all the edges in nondecreasing order of their weight.
• Edge with minimum weight is selected and its feasibility is tested.
• If inclusion of the edge to a partial solution does not form the cycle, then the edge is feasible and added to the partial solution.
• If is not feasible then skip it and check for the next edge. The process is repeated until all edges are scanned.
• Let, list unvisited edges UE = {e1, e2, e3, . . . , em}, be the edges sorted by increasing order of their weight.

1.     Select minimum weight edge emin from input graph G, which is not already added.

2.     If the addition of edge emin to a partial solution does not form a cycle, add it. Otherwise look for next minimum weight edge until we get the feasible edge. Remove checked edges from E.

3.     Go to step 1 and repeat the procedure until all edges in E are scanned.

## Algorithm for Kruskal’s Algorithm

Algorithm for Kruskal’s approach is shown below:

Algorithm KUSKAL_MST(G)
// Description : Find minimum spanning tree of graph G of n vertices
// Input : Weighted undirected graph G
// Output : Minimum spanning tree of G

MST ← Φ
for each v ∈ V do
MAKE-SET(v)
end

for  MAKE-SET(v) do
if FIND-SET(u) ≠ FIND-SET(v) then
MST ← MST ∪ (u, v)
UNION(u, v)
end
end

FUNCTION MAKE-SET(x)
if x is not already present then
x.parent ← x
x.rank ← 0
end

if x.parent ≠ x  then
x.parent ← FIND(x.parent)
end
return x.parent

FUNCTION UNION(x, y)
xRoot ← FIND(x)
yRoot ← FIND(y)
if xRoot == yRoot then
return
end

if xRoot.rank < yRoot.rank then
xRoot.parent ← yRoot
else if yRoot.rank < xRoot.rank then
yRoot.parent ← xRoot
else
xRoot.parent ← yRoot
yRoot.rank ← yRoot.rank + 1
end

## Time complexity of Kruskal’s Algorithm

• Using Disjoint-set data structures, with |E| edges and |V| vertices in the graph, Kruskal’s algorithm runs in O(|E| log2|E|)  or O(|E| log2|V|) time, both are identical. For the dense graph, |E| is at most |V2|. So,
log2|E| = log2|V2| = 2log2|V| ≈ log2|V|
• Sort edges using comparison based algorithm, which could sort it in O(|E|log2|E|) time. Selection and feasibility checking of the edge is done in O(|E|) time. Thus total running time is given as
O(|E| + |E| log |E|) = O(|E| log |E|).

## Examples

Example: Find the cost of Minimal Spanning Tree of the given graph by using Kruskal’s Algorithm

Solution:

• Kruskal’s algorithm sorts the edges according to decreasing order of their weight. Sorted edges are listed in following table:
• One by one edge is added to a partial solution if it is not forming the cycle.
• Initially, set of unvisited edges UE = {<1, 2>, <3, 5>, <1, 3>, <2, 3>, <3, 4>, <4, 5>, <2, 4>}

Example: Find out minimum cost spanning tree using KRUSKAL algorithm

Solution:

Graph representation of given data is shown in following Figure.

• Kruskal’s algorithm sorts the edges according to decreasing order of their weight. Sorted edges are listed in the following table:
• One by one edge is added to a partial solution if it is not forming the cycle.
• Initially, set of unvisited edges UE = {<V1, V7>, <V3, V4>, <V2, V7>, <V4, V5>, <V3, V7>, <V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>}

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :