Minimum cost to connect all cities | Function to find out minimum valued node among the nodes which are not yet included in MST ; Loop through all the values of the nodes which are not yet included in MST and find the minimum valued one . ; Function to find out the MST and the cost of the MST . ; Array to store the parent node of a particular node . ; Array to store key value of each node . ; Boolean Array to hold bool values whether a node is included in MST or not . ; Set all the key values to infinite and none of the nodes is included in MST . ; Start to find the MST from node 0. Parent of node 0 is none so set - 1. key value or minimum cost to reach 0 th node from 0 th node is 0. ; Find the rest n - 1 nodes of MST . ; First find out the minimum node among the nodes which are not yet included in MST . ; Now the uth node is included in MST . ; Update the values of neighbor nodes of u which are not yet included in MST . ; Find out the cost by adding the edge values of MST . ; Input 1 ; Input 2
function minnode ( n , keyval , mstset ) { let mini = Number . MAX_VALUE ; let mini_index = 0 ; for ( let i = 0 ; i < n ; i ++ ) { if ( mstset [ i ] == false && keyval [ i ] < mini ) { mini = keyval [ i ] ; mini_index = i ; } } return mini_index ; } function findcost ( n , city ) { let parent = Array ( n ) . fill ( 0 ) ; let keyval = Array ( n ) . fill ( 0 ) ; let mstset = Array ( n ) . fill ( 0 ) ; for ( let i = 0 ; i < n ; i ++ ) { keyval [ i ] = Number . MAX_VALUE ; mstset [ i ] = false ; } parent [ 0 ] = - 1 ; keyval [ 0 ] = 0 ; for ( let i = 0 ; i < n - 1 ; i ++ ) { let u = minnode ( n , keyval , mstset ) ; mstset [ u ] = true ; for ( let v = 0 ; v < n ; v ++ ) { if ( city [ u ] [ v ] > 0 && mstset [ v ] == false && city [ u ] [ v ] < keyval [ v ] ) { keyval [ v ] = city [ u ] [ v ] ; parent [ v ] = u ; } } } let cost = 0 ; for ( let i = 1 ; i < n ; i ++ ) cost += city [ parent [ i ] ] [ i ] ; document . write ( cost + " " ) ; } let n1 = 5 ; let city1 = [ [ 0 , 1 , 2 , 3 , 4 ] , [ 1 , 0 , 5 , 0 , 7 ] , [ 2 , 5 , 0 , 6 , 0 ] , [ 3 , 0 , 6 , 0 , 0 ] , [ 4 , 7 , 0 , 0 , 0 ] ] ; findcost ( n1 , city1 ) ; let n2 = 6 ; let city2 = [ [ 0 , 1 , 1 , 100 , 0 , 0 ] , [ 1 , 0 , 1 , 0 , 0 , 0 ] , [ 1 , 1 , 0 , 0 , 0 , 0 ] , [ 100 , 0 , 0 , 0 , 2 , 2 ] , [ 0 , 0 , 0 , 2 , 0 , 2 ] , [ 0 , 0 , 0 , 2 , 2 , 0 ] ] ; findcost ( n2 , city2 ) ;