Minimize cost to color all the vertices of an Undirected Graph using given operation | Java 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 java . util . * ; class GFG { static final int MAX = 10 ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] adj = new Vector [ MAX ] ; static int min_cost_node ; static void addEdge ( int u , int v ) { adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } static void dfs ( int v , int cost [ ] , boolean vis [ ] ) { vis [ v ] = true ; min_cost_node = Math . min ( min_cost_node , cost [ v - 1 ] ) ; for ( int i = 0 ; i < adj [ v ] . size ( ) ; i ++ ) { if ( vis [ adj [ v ] . get ( i ) ] == false ) { dfs ( adj [ v ] . get ( i ) , cost , vis ) ; } } } static int minimumCost ( int V , int cost [ ] ) { boolean [ ] vis = new boolean [ V + 1 ] ; Arrays . fill ( vis , false ) ; int min_cost = 0 ; for ( int i = 1 ; i <= V ; i ++ ) { if ( ! vis [ i ] ) { min_cost_node = Integer . MAX_VALUE ; dfs ( i , cost , vis ) ; min_cost += min_cost_node ; } } return min_cost ; } public static void main ( String [ ] args ) { int V = 6 , E = 5 ; int cost [ ] = { 12 , 25 , 8 , 11 , 10 , 7 } ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 2 ) ; addEdge ( 2 , 5 ) ; addEdge ( 4 , 6 ) ; int min_cost = minimumCost ( V , cost ) ; System . out . print ( min_cost + "NEW_LINE"); } }