Find weight of MST in a complete graph with edge | Java Program to find weight of minimum spanning tree in a complete graph where edges have weight either 0 or 1 ; 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
import java . util . * ; class GFG { static HashMap < Integer , Integer > [ ] g = new HashMap [ 200005 ] ; static HashSet < Integer > s = new HashSet < > ( ) ; static HashSet < Integer > ns = new HashSet < > ( ) ; static void dfs ( int x ) { Vector < Integer > v = new Vector < > ( ) ; v . clear ( ) ; ns . clear ( ) ; for ( int it : s ) { if ( g [ x ] . get ( it ) != null ) { v . add ( it ) ; } else { ns . add ( it ) ; } } s = ns ; for ( int i : v ) { dfs ( i ) ; } } static void weightOfMST ( int N ) { int cnt = 0 ; for ( int i = 1 ; i <= N ; ++ i ) { s . add ( i ) ; } Vector < Integer > qt = new Vector < > ( ) ; for ( int t : s ) qt . add ( t ) ; while ( ! qt . isEmpty ( ) ) { ++ cnt ; int t = qt . get ( 0 ) ; qt . remove ( 0 ) ; dfs ( t ) ; } System . out . print ( cnt - 4 ) ; } public static void main ( String [ ] args ) { int N = 6 , M = 11 ; int edges [ ] [ ] = { { 1 , 3 } , { 1 , 4 } , { 1 , 5 } , { 1 , 6 } , { 2 , 3 } , { 2 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 4 } , { 3 , 5 } , { 3 , 6 } } ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < M ; ++ i ) { int u = edges [ i ] [ 0 ] ; int v = edges [ i ] [ 1 ] ; g [ u ] . put ( v , 1 ) ; g [ v ] . put ( u , 1 ) ; } weightOfMST ( N ) ; } }