d | Python3 program to find the size of the minimum dominating set of the tree ; Definition of a tree node ; Helper function that allocates a new node ; DP array to precompute and store the results ; minDominatingSettion to return the size of the minimum dominating set of the array ; Base case ; Setting the compulsory value if needed ; Check if the answer is already computed ; If it is compulsory to select the node ; Choose the node and set its children as covered ; If it is covered ; If the current node is neither covered nor needs to be selected compulsorily ; Store the result ; Driver code ; Constructing the tree
N = 1005 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT node = Node ( data ) NEW_LINE return node NEW_LINE DEDENT dp = [ [ [ - 1 for i in range ( 5 ) ] for j in range ( 5 ) ] for k in range ( N ) ] ; NEW_LINE def minDominatingSet ( root , covered , compulsory ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( not root . left and not root . right and not covered ) : NEW_LINE INDENT compulsory = True ; NEW_LINE DEDENT if ( dp [ root . data ] [ covered ] [ compulsory ] != - 1 ) : NEW_LINE INDENT return dp [ root . data ] [ covered ] [ compulsory ] ; NEW_LINE DEDENT if ( compulsory ) : NEW_LINE INDENT dp [ root . data ] [ covered ] [ compulsory ] = 1 + minDominatingSet ( root . left , 1 , 0 ) + minDominatingSet ( root . right , 1 , 0 ) ; NEW_LINE return dp [ root . data ] [ covered ] [ compulsory ] NEW_LINE DEDENT if ( covered ) : NEW_LINE INDENT dp [ root . data ] [ covered ] [ compulsory ] = min ( 1 + minDominatingSet ( root . left , 1 , 0 ) + minDominatingSet ( root . right , 1 , 0 ) , minDominatingSet ( root . left , 0 , 0 ) + minDominatingSet ( root . right , 0 , 0 ) ) ; NEW_LINE return dp [ root . data ] [ covered ] [ compulsory ] NEW_LINE DEDENT ans = 1 + minDominatingSet ( root . left , 1 , 0 ) + minDominatingSet ( root . right , 1 , 0 ) ; NEW_LINE if ( root . left ) : NEW_LINE INDENT ans = min ( ans , minDominatingSet ( root . left , 0 , 1 ) + minDominatingSet ( root . right , 0 , 0 ) ) ; NEW_LINE DEDENT if ( root . right ) : NEW_LINE INDENT ans = min ( ans , minDominatingSet ( root . left , 0 , 0 ) + minDominatingSet ( root . right , 0 , 1 ) ) ; NEW_LINE DEDENT dp [ root . data ] [ covered ] [ compulsory ] = ans ; NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) ; NEW_LINE root . left = newNode ( 2 ) ; NEW_LINE root . left . left = newNode ( 3 ) ; NEW_LINE root . left . right = newNode ( 4 ) ; NEW_LINE root . left . left . left = newNode ( 5 ) ; NEW_LINE root . left . left . left . left = newNode ( 6 ) ; NEW_LINE root . left . left . left . right = newNode ( 7 ) ; NEW_LINE root . left . left . left . right . right = newNode ( 10 ) ; NEW_LINE root . left . left . left . left . left = newNode ( 8 ) ; NEW_LINE root . left . left . left . left . right = newNode ( 9 ) ; NEW_LINE print ( minDominatingSet ( root , 0 , 0 ) ) NEW_LINE DEDENT