Prim 's Algorithm (Simple Implementation for Adjacency Matrix Representation) | JavaScript implementation to find minimum spanning tree for adjacency representation . ; Returns true if edge u - v is a valid edge to be include in MST . An edge is valid if one end is already included in MST and other is not in MST . ; Include first vertex in MST ; Keep adding edges while number of included edges does not become V - 1. ; Find minimum weight valid edge . ; Let us create the following graph 2 3 ( 0 ) -- ( 1 ) -- ( 2 ) | / \ | 6 | 8 / \ 5 | 7 | / \ | ( 3 ) -- -- -- - ( 4 ) 9 ; Print the solution
let V = 5 ; let let_MAX = Number . MAX_VALUE ; function isValidEdge ( u , v , inMST ) { if ( u == v ) return false ; if ( inMST [ u ] == false && inMST [ v ] == false ) return false ; else if ( inMST [ u ] == true && inMST [ v ] == true ) return false ; return true ; } function primMST ( cost ) { let inMST = Array ( V ) . fill ( false ) ; inMST [ 0 ] = true ; let edge_count = 0 , mincost = 0 ; while ( edge_count < V - 1 ) { let min = let_MAX , a = - 1 , b = - 1 ; for ( let i = 0 ; i < V ; i ++ ) { for ( let j = 0 ; j < V ; j ++ ) { if ( cost [ i ] [ j ] < min ) { if ( isValidEdge ( i , j , inMST ) ) { min = cost [ i ] [ j ] ; a = i ; b = j ; } } } } if ( a != - 1 && b != - 1 ) { document . write ( " " + edge_count ++ + " " + a + " " + b + " " + " " + min + " " ) ; mincost = mincost + min ; inMST [ b ] = inMST [ a ] = true ; } } document . write ( " " ) ; document . write ( " " ) ; document . write ( " " + mincost ) ; } let cost = [ [ let_MAX , 2 , let_MAX , 6 , let_MAX ] , [ 2 , let_MAX , 3 , 8 , 5 ] , [ let_MAX , 3 , let_MAX , let_MAX , 7 ] , [ 6 , 8 , let_MAX , let_MAX , 9 ] , [ let_MAX , 5 , 7 , 9 , let_MAX ] ] ; primMST ( cost ) ;