Kruskal 's Algorithm (Simple Implementation for Adjacency Matrix) | Find set of vertex i ; Does union of i and j . It returns false if i and j are already in same set . ; Finds MST using Kruskal 's algorithm ; Initialize sets of disjoint sets ; Include minimum weight edges one by one ; Let us create the following graph 2 3 ( 0 ) -- ( 1 ) -- ( 2 ) | / \ | 6 | 8 / \ 5 | 7 | / \ | ( 3 ) -- -- -- - ( 4 ) 9 ; Print the solution
def find ( i ) : NEW_LINE INDENT while parent [ i ] != i : NEW_LINE INDENT i = parent [ i ] NEW_LINE DEDENT return i NEW_LINE DEDENT def union ( i , j ) : NEW_LINE INDENT a = find ( i ) NEW_LINE b = find ( j ) NEW_LINE parent [ a ] = b NEW_LINE DEDENT def kruskalMST ( cost ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT parent [ i ] = i NEW_LINE DEDENT edge_count = 0 NEW_LINE while edge_count < V - 1 : NEW_LINE INDENT min = INF NEW_LINE a = - 1 NEW_LINE b = - 1 NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT if find ( i ) != find ( j ) and cost [ i ] [ j ] < min : NEW_LINE INDENT min = cost [ i ] [ j ] NEW_LINE a = i NEW_LINE b = j NEW_LINE DEDENT DEDENT DEDENT union ( a , b ) NEW_LINE print ( ' Edge ▁ { } : ( { } , ▁ { } ) ▁ cost : { } ' . format ( edge_count , a , b , min ) ) NEW_LINE edge_count += 1 NEW_LINE mincost += min NEW_LINE DEDENT print ( " Minimum ▁ cost = ▁ { } " . format ( mincost ) ) NEW_LINE DEDENT V = 5 NEW_LINE parent = [ i for i in range ( V ) ] NEW_LINE INF = float ( ' inf ' ) NEW_LINE cost = [ [ INF , 2 , INF , 6 , INF ] , [ 2 , INF , 3 , 8 , 5 ] , [ INF , 3 , INF , INF , 7 ] , [ 6 , 8 , INF , INF , 9 ] , [ INF , 5 , 7 , 9 , INF ] ] NEW_LINE kruskalMST ( cost ) NEW_LINE