Spanning Tree With Maximum Degree ( Using Kruskal 's Algorithm) | par and rank will store the parent and rank of particular node in the Union Find Algorithm ; Find function of Union Find Algorithm ; Union function of Union Find Algorithm ; Function to find the required spanning tree ; Initialising parent of a node by itself ; Variable to store the node with maximum degree ; Finding the node with maximum degree ; Union of all edges incident on vertex with maximum degree ; Carrying out normal Kruskal Algorithm ; Number of nodes ; Number of edges ; ArrayList to store the graph ; Array to store the degree of each node in the graph ; Add edges and update degrees
let par , rank ; function find ( x ) { if ( par [ x ] != x ) par [ x ] = find ( par [ x ] ) ; return par [ x ] ; } function union ( u , v ) { let x = find ( u ) ; let y = find ( v ) ; if ( x == y ) return ; if ( rank [ x ] > rank [ y ] ) par [ y ] = x ; else if ( rank [ x ] < rank [ y ] ) par [ x ] = y ; else { par [ x ] = y ; rank [ y ] ++ ; } } function findSpanningTree ( deg , n , m , g ) { par = new Array ( n + 1 ) ; rank = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) par [ i ] = i ; let max = 1 ; for ( let i = 2 ; i <= n ; i ++ ) if ( deg [ i ] > deg [ max ] ) max = i ; for ( let v = 0 ; v < g [ max ] . length ; v ++ ) { document . write ( max + " " + g [ max ] [ v ] + " " ) ; union ( max , g [ max ] [ v ] ) ; } for ( let u = 1 ; u <= n ; u ++ ) { for ( let v = 0 ; v < g [ u ] . length ; v ++ ) { let x = find ( u ) ; let y = find ( g [ u ] [ v ] ) ; if ( x == y ) continue ; union ( x , y ) ; document . write ( u + " " + g [ u ] [ v ] + " " ) ; } } } let n = 5 ; let m = 5 ; let g = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) g [ i ] = [ ] ; let deg = new Array ( n + 1 ) ; deg . fill ( 0 ) ; g [ 1 ] . push ( 2 ) ; g [ 2 ] . push ( 1 ) ; deg [ 1 ] ++ ; deg [ 2 ] ++ ; g [ 1 ] . push ( 5 ) ; g [ 5 ] . push ( 1 ) ; deg [ 1 ] ++ ; deg [ 5 ] ++ ; g [ 2 ] . push ( 3 ) ; g [ 3 ] . push ( 2 ) ; deg [ 2 ] ++ ; deg [ 3 ] ++ ; g [ 5 ] . push ( 3 ) ; g [ 3 ] . push ( 5 ) ; deg [ 3 ] ++ ; deg [ 5 ] ++ ; g [ 3 ] . push ( 4 ) ; g [ 4 ] . push ( 3 ) ; deg [ 3 ] ++ ; deg [ 4 ] ++ ; findSpanningTree ( deg , n , m , g ) ;