Spanning Tree With Maximum Degree ( Using Kruskal 's Algorithm) | Python3 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
from typing import List NEW_LINE par = [ ] NEW_LINE rnk = [ ] NEW_LINE def find ( x : int ) -> int : NEW_LINE INDENT global par NEW_LINE if ( par [ x ] != x ) : NEW_LINE INDENT par [ x ] = find ( par [ x ] ) NEW_LINE DEDENT return par [ x ] NEW_LINE DEDENT def Union ( u : int , v : int ) -> None : NEW_LINE INDENT global par , rnk NEW_LINE x = find ( u ) NEW_LINE y = find ( v ) NEW_LINE if ( x == y ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( rnk [ x ] > rnk [ y ] ) : NEW_LINE INDENT par [ y ] = x NEW_LINE DEDENT elif ( rnk [ x ] < rnk [ y ] ) : NEW_LINE INDENT par [ x ] = y NEW_LINE DEDENT else : NEW_LINE INDENT par [ x ] = y NEW_LINE rnk [ y ] += 1 NEW_LINE DEDENT DEDENT def findSpanningTree ( deg : List [ int ] , n : int , m : int , g : List [ List [ int ] ] ) -> None : NEW_LINE INDENT global rnk , par NEW_LINE par = [ i for i in range ( n + 1 ) ] NEW_LINE rnk = [ 0 ] * ( n + 1 ) NEW_LINE max = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( deg [ i ] > deg [ max ] ) : NEW_LINE INDENT max = i NEW_LINE DEDENT DEDENT for v in g [ max ] : NEW_LINE INDENT print ( " { } ▁ { } " . format ( max , v ) ) NEW_LINE Union ( max , v ) NEW_LINE DEDENT for u in range ( 1 , n + 1 ) : NEW_LINE INDENT for v in g [ u ] : NEW_LINE INDENT x = find ( u ) NEW_LINE y = find ( v ) NEW_LINE if ( x == y ) : NEW_LINE INDENT continue NEW_LINE DEDENT Union ( x , y ) NEW_LINE print ( " { } ▁ { } " . format ( u , v ) ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE m = 5 NEW_LINE g = [ [ ] for _ in range ( n + 1 ) ] NEW_LINE deg = [ 0 ] * ( n + 1 ) NEW_LINE g [ 1 ] . append ( 2 ) NEW_LINE g [ 2 ] . append ( 1 ) NEW_LINE deg [ 1 ] += 1 NEW_LINE deg [ 2 ] += 1 NEW_LINE g [ 1 ] . append ( 5 ) NEW_LINE g [ 5 ] . append ( 1 ) NEW_LINE deg [ 1 ] += 1 NEW_LINE deg [ 5 ] += 1 NEW_LINE g [ 2 ] . append ( 3 ) NEW_LINE g [ 3 ] . append ( 2 ) NEW_LINE deg [ 2 ] += 1 NEW_LINE deg [ 3 ] += 1 NEW_LINE g [ 5 ] . append ( 3 ) NEW_LINE g [ 3 ] . append ( 5 ) NEW_LINE deg [ 3 ] += 1 NEW_LINE deg [ 5 ] += 1 NEW_LINE g [ 3 ] . append ( 4 ) NEW_LINE g [ 4 ] . append ( 3 ) NEW_LINE deg [ 3 ] += 1 NEW_LINE deg [ 4 ] += 1 NEW_LINE findSpanningTree ( deg , n , m , g ) NEW_LINE DEDENT