Minimize cost to color all the vertices of an Undirected Graph using given operation | C # 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 readonly cost ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static readonly int MAX = 10 ; static List < int > [ ] adj = new List < int > [ 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 , bool [ ] vis ) { vis [ v ] = true ; min_cost_node = Math . Min ( min_cost_node , cost [ v - 1 ] ) ; for ( int i = 0 ; i < adj [ v ] . Count ; i ++ ) { if ( vis [ adj [ v ] [ i ] ] == false ) { dfs ( adj [ v ] [ i ] , cost , vis ) ; } } } static int minimumCost ( int V , int [ ] cost ) { bool [ ] vis = new bool [ V + 1 ] ; int min_cost = 0 ; for ( int i = 1 ; i <= V ; i ++ ) { if ( ! vis [ i ] ) { min_cost_node = int . MaxValue ; dfs ( i , cost , vis ) ; min_cost += min_cost_node ; } } return min_cost ; } public static void Main ( String [ ] args ) { int V = 6 ; int [ ] cost = { 12 , 25 , 8 , 11 , 10 , 7 } ; for ( int i = 0 ; i < adj . Length ; i ++ ) adj [ i ] = new List < int > ( ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 2 ) ; addEdge ( 2 , 5 ) ; addEdge ( 4 , 6 ) ; int min_cost = minimumCost ( V , cost ) ; Console . Write ( min_cost + " STRNEWLINE " ) ; } }