Kruskal 's Algorithm (Simple Implementation for Adjacency Matrix) | Simple Javascript implementation for Kruskal 's algorithm ; 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
var V = 5 ; var parent = Array ( V ) . fill ( 0 ) ; var INF = 1000000000 ; function find ( i ) { while ( parent [ i ] != i ) i = parent [ i ] ; return i ; } function union1 ( i , j ) { var a = find ( i ) ; var b = find ( j ) ; parent [ a ] = b ; } function kruskalMST ( cost ) { for ( var i = 0 ; i < V ; i ++ ) parent [ i ] = i ; var edge_count = 0 ; while ( edge_count < V - 1 ) { var min = INF , a = - 1 , b = - 1 ; for ( var i = 0 ; i < V ; i ++ ) { for ( var j = 0 ; j < V ; j ++ ) { if ( find ( i ) != find ( j ) && cost [ i ] [ j ] < min ) { min = cost [ i ] [ j ] ; a = i ; b = j ; } } } union1 ( a , b ) ; document . write ( ` ${ edge_count ++ } ${ a } ${ b } ${ min } ` ) ; mincost += min ; } document . write ( ` ${ mincost } ` ) ; } var 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 ] ] ; kruskalMST ( cost ) ;