Minimize cost to color all the vertices of an Undirected Graph using given operation | Python3 program to find the minimum cost to color all vertices of an Undirected Graph ; Function to add edge in the given graph ; Function to perform DFS traversal and find the node with minimum cost ; Update the minimum cost ; Recur for all connected nodes ; Function to calculate and return the minimum cost of coloring all vertices of the Undirected Graph ; Marks if a vertex is visited or not ; Perform DFS traversal ; If vertex is not visited ; Update minimum cost ; Return the final cost ; Driver Code
import sys NEW_LINE MAX = 10 NEW_LINE adj = [ [ ] for i in range ( MAX ) ] NEW_LINE def addEdge ( u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def dfs ( v , cost , vis , min_cost_node ) : NEW_LINE INDENT vis [ v ] = True NEW_LINE min_cost_node = min ( min_cost_node , cost [ v - 1 ] ) NEW_LINE for i in range ( len ( adj [ v ] ) ) : NEW_LINE INDENT if ( vis [ adj [ v ] [ i ] ] == False ) : NEW_LINE INDENT min_cost_node = dfs ( adj [ v ] [ i ] , cost , vis , min_cost_node ) NEW_LINE DEDENT DEDENT return min_cost_node NEW_LINE DEDENT def minimumCost ( V , cost ) : NEW_LINE INDENT vis = [ False for i in range ( V + 1 ) ] NEW_LINE min_cost = 0 NEW_LINE for i in range ( 1 , V + 1 ) : NEW_LINE INDENT if ( not vis [ i ] ) : NEW_LINE INDENT min_cost_node = sys . maxsize NEW_LINE min_cost_node = dfs ( i , cost , vis , min_cost_node ) NEW_LINE min_cost += min_cost_node NEW_LINE DEDENT DEDENT return min_cost NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT V = 6 NEW_LINE E = 5 NEW_LINE cost = [ 12 , 25 , 8 , 11 , 10 , 7 ] NEW_LINE addEdge ( 1 , 2 ) NEW_LINE addEdge ( 1 , 3 ) NEW_LINE addEdge ( 3 , 2 ) NEW_LINE addEdge ( 2 , 5 ) NEW_LINE addEdge ( 4 , 6 ) NEW_LINE min_cost = minimumCost ( V , cost ) NEW_LINE print ( min_cost ) NEW_LINE DEDENT