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 final cost ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  10 NEW_LINE vector < int > adj [ MAX ] ; void addEdge ( int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void dfs ( int v , int cost [ ] , bool vis [ ] , int & min_cost_node ) { vis [ v ] = true ; min_cost_node = min ( min_cost_node , cost [ v - 1 ] ) ; for ( int i = 0 ; i < adj [ v ] . size ( ) ; i ++ ) { if ( vis [ adj [ v ] [ i ] ] == false ) { dfs ( adj [ v ] [ i ] , cost , vis , min_cost_node ) ; } } } int minimumCost ( int V , int cost [ ] ) { bool vis [ V + 1 ] ; memset ( vis , false , sizeof ( vis ) ) ; int min_cost = 0 ; for ( int i = 1 ; i <= V ; i ++ ) { if ( ! vis [ i ] ) { int min_cost_node = INT_MAX ; dfs ( i , cost , vis , min_cost_node ) ; min_cost += min_cost_node ; } } return min_cost ; } int main ( ) { int V = 6 , E = 5 ; int cost [ ] = { 12 , 25 , 8 , 11 , 10 , 7 } ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 3 , 2 ) ; addEdge ( 2 , 5 ) ; addEdge ( 4 , 6 ) ; int min_cost = minimumCost ( V , cost ) ; cout << min_cost << endl ; return 0 ; }