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

Kruskal’s Algorithm example

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>
Cost1233456
  • 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 solutionUpdated 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

EdgeCostEdgeCost
(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 exmple
  • 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>
Cost1347915
Edge<V4, V7><V1, V2><V1, V6><V5, V7><V5, V6><V6, V7>
Cost162023252836
  • 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 solutionUpdated 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

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


Additional Reading: Wiki

Leave a Reply

Your email address will not be published. Required fields are marked *