Find weight of MST in a complete graph with edge | To store the edges of the given graph ; A utility function to perform DFS Traversal ; Check those vertices which are stored in the set ; Vertices are included if the weight of edge is 0 ; A utility function to find the weight of Minimum Spanning Tree ; To count the connected components ; Inserting the initial vertices in the set ; Traversing vertices stored in the set and Run DFS Traversal for each vertices ; Incrementing the zero weight connected components ; DFS Traversal for every vertex remove ; Driver 's Code ; Insert edges ; Function call find the weight of Minimum Spanning Tree
let g = new Array ( 200005 ) ; for ( let i = 0 ; i < 200005 ; i ++ ) g [ i ] = new Map ( ) ; let s = new Set ( ) ; let ns = new Set ( ) ; function dfs ( x ) { let v = [ ] ; for ( let it of s . values ( ) ) { if ( g [ x ] . get ( it ) != null ) { v . push ( it ) ; } else { ns . add ( it ) ; } } s = ns ; for ( let i of v . values ( ) ) { dfs ( i ) ; } } function weightOfMST ( N ) { let cnt = 0 ; for ( let i = 1 ; i <= N ; ++ i ) { s . add ( i ) ; } let qt = [ ] for ( let t of s . values ( ) ) qt . push ( t ) ; while ( qt . length != 0 ) { ++ cnt ; let t = qt [ 0 ] ; qt . shift ( ) ; dfs ( t ) ; } document . write ( cnt - 4 ) ; } let N = 6 , M = 11 ; let edges = [ [ 1 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 1 , 6 ] , [ 2 , 3 ] , [ 2 , 4 ] , [ 2 , 5 ] , [ 2 , 6 ] , [ 3 , 4 ] , [ 3 , 5 ] , [ 3 , 6 ] ] ; for ( let i = 0 ; i < M ; ++ i ) { let u = edges [ i ] [ 0 ] ; let v = edges [ i ] [ 1 ] ; g [ u ] . set ( v , 1 ) ; g [ v ] . set ( u , 1 ) ; } weightOfMST ( N ) ;