Spanning Tree With Maximum Degree ( Using Kruskal 's Algorithm) | Java implementation of the approach ; 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 ; Driver code ; 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
import java . util . * ; public class GFG { static int par [ ] , rank [ ] ; static int find ( int x ) { if ( par [ x ] != x ) par [ x ] = find ( par [ x ] ) ; return par [ x ] ; } static void union ( int u , int v ) { int x = find ( u ) ; int 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 ] ++ ; } } static void findSpanningTree ( int deg [ ] , int n , int m , ArrayList < Integer > g [ ] ) { par = new int [ n + 1 ] ; rank = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) par [ i ] = i ; int max = 1 ; for ( int i = 2 ; i <= n ; i ++ ) if ( deg [ i ] > deg [ max ] ) max = i ; for ( int v : g [ max ] ) { System . out . println ( max + " ▁ " + v ) ; union ( max , v ) ; } for ( int u = 1 ; u <= n ; u ++ ) { for ( int v : g [ u ] ) { int x = find ( u ) ; int y = find ( v ) ; if ( x == y ) continue ; union ( x , y ) ; System . out . println ( u + " ▁ " + v ) ; } } } public static void main ( String args [ ] ) { int n = 5 ; int m = 5 ; ArrayList < Integer > g [ ] = new ArrayList [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) g [ i ] = new ArrayList < > ( ) ; int deg [ ] = new int [ n + 1 ] ; g [ 1 ] . add ( 2 ) ; g [ 2 ] . add ( 1 ) ; deg [ 1 ] ++ ; deg [ 2 ] ++ ; g [ 1 ] . add ( 5 ) ; g [ 5 ] . add ( 1 ) ; deg [ 1 ] ++ ; deg [ 5 ] ++ ; g [ 2 ] . add ( 3 ) ; g [ 3 ] . add ( 2 ) ; deg [ 2 ] ++ ; deg [ 3 ] ++ ; g [ 5 ] . add ( 3 ) ; g [ 3 ] . add ( 5 ) ; deg [ 3 ] ++ ; deg [ 5 ] ++ ; g [ 3 ] . add ( 4 ) ; g [ 4 ] . add ( 3 ) ; deg [ 3 ] ++ ; deg [ 4 ] ++ ; findSpanningTree ( deg , n , m , g ) ; } }