Kruskal’s Algorithm
Introduction to Kruskal’s Algorithm
Kruskal’s Algorithm Problem: Find the minimum spanning tree from a given weighted, undirected graph G = <V, E, W>
- Joseph Kruskal has suggested a greedy approach to find MST from a given weighted, undirected graph.
- The algorithm first sorts all the edges in the nondecreasing order of their weight.
- An edge with minimum weight is selected and its feasibility is tested.
- If the 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 the 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 the 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 the following table:
Edge | <1, 2> | <3, 5> | <1, 3> | <2, 3> | <3, 4> | <4, 5> | <2, 4> |
Cost | 1 | 2 | 3 | 3 | 4 | 5 | 6 |
- 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>}
Partial solution | Updated UE |
Step 1: Minimum cost edge is <1, 2>, so add it to MST and remove it from UE | UE = { <3, 5>, <1, 3>, <2, 3>, <3, 4>, <4, 5>, <2, 4> } |
Step 2: Minimum cost edge is <3, 5>, so add it to MST and remove it from UE | UE = { <1, 3>, <2, 3>, <3, 4>, <4, 5>, <2, 4> } |
Step 3: Minimum cost edge is <1, 3>, so add it to MST and remove it from UE | UE = { <2, 3>, <3, 4>, <4, 5>, <2, 4> } |
Step 4 : Minimum cost edge is <2, 3>, but its inclusion creates a cycle so remove it from UE So, UE = { <3, 4>, <4, 5>, <2, 4> } The next minimum cost edge is <3, 4> and its inclusion does not form a cycle, so add it to MST and remove it from UE | UE = { <4, 5>, <2, 4> } |
Step 5 : Minimum cost edge is <4, 5>, but its inclusion creates a cycle so remove it from UE So, UE = { <2, 4> } The minimum cost edge is <2, 4>, but its inclusion creates a cycle so remove it from UE So, UE = { } | UE is empty so the tree generated in step 4 is the minimum spanning tree of a given graph. Let w(u, v) represent the weight of the edge (u, v) Cost of solution: w(1, 2) + w(1, 3) + w(3, 4) + w(3, 5) = 1 + 3 + 4 + 2 = 10 |
Example: Find out the minimum cost-spanning tree using the KRUSKAL algorithm
Edge | Cost | Edge | Cost |
(V1,V7) | 1 | (V4,V5) | 7 |
(V3,V4) | 3 | (V1,V2) | 20 |
(V2,V7) | 4 | (V1,V6) | 23 |
(V3,V7) | 9 | (V5,V7) | 25 |
(V2,V3) | 15 | (V5,V6) | 28 |
(V4,V7) | 16 | (V6,V7) | 36 |
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:
Edge | <V1, V7> | <V3, V4> | <V2, V7> | <V4, V5> | <V3, V7> | <V2, V3> |
Cost | 1 | 3 | 4 | 7 | 9 | 15 |
Edge | <V4, V7> | <V1, V2> | <V1, V6> | <V5, V7> | <V5, V6> | <V6, V7> |
Cost | 16 | 20 | 23 | 25 | 28 | 36 |
- 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>}
Partial solution | Updated UE |
Step 1: Minimum cost edge is <V1, V7>, so add it to MST and remove from UE | UE = {<V3, V4>, <V2, V7>, <V4, V5>, <V3, V7>, <V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 2: Next minimum cost edge is <V3, V4>, so add it to MST and remove from UE | UE = {<V2, V7>, <V4, V5>, <V3, V7>, <V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 3: Next minimum cost edge is <V2, V7>, so add it to MST and remove from UE | UE = {<V4, V5>, <V3, V7>, <V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 4: Next minimum cost edge is <V4, V5>, so add it to MST and remove from UE | UE = {<V3, V7>, <V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 5: Next minimum cost edge is <V3, V7>, so add it to MST and remove from UE | UE = {<V2, V3>, <V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 6: Next minimum cost edge is <V2, V3>, but its inclusion creates a cycle so remove it from UE. | UE = {<V4, V7>, <V1, V2>, <V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 7: Similarly, the next minimum cost edges are <V4, V7> and <V1, V2> form cycle so remove them from UE. | UE = {<V1, V6>, <V5, V7>, <V5, V6>, <V6, V7>} |
Step 8: Next minimum cost edge is <V1, V6>, so add it to MST and remove from UE | UE = {<V5, V7>, <V5, V6>, <V6, V7>} |
Step 9: Next minimum cost edge is <V5, V7>, but its inclusion creates cycle so remove it from UE. So, UE = {<V5, V6>, <V6, V7>} Similarly, next minimum cost edges <V5, V6> and <V6, V7> form cycle so remove them from UE. So, UE = { } | UE is empty so the tree generated in step 4 is the minimum spanning tree of given graph. Let w(u, v) represent the weight of edge (u, v) Cost of solution: w(V1, V6) + w(V1, V7) + w(V2, V7) + w(V7, V3) + w(V3, V4) + w(V4, V5) = 23 + 1 + 4 + 9 + 3 + 7 = 47 |
Some Popular Problems Solved by Greddy Algorithm
Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :
- Binary Knapsack Problem
- Fractional Knapsack Problem
- Job Scheduling Problem
- Activity Selection Problem
- Huffman Coding
- Optimal Storage on Tapes
- Optimal Merge Pattern
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm
Additional Reading: Wiki