You are given an undirected graph and two colors, black and white.  write  a program to find the maximum number of nodes that can be colored with black such way that no two connected nodes colored with black. For example below undirected graph ,the maximum number of nodes that can be colored with black would be 3.

Graph coloring backtracking problem

#include <iostream>
#include<list>
using namespace std;

// data structure for undirected graph ,adjacency list
class G
{
	int no_of_nodes;
	list<int> *adj_list;
public:
	G(int no_of_nodes)
	{
		this->no_of_nodes = no_of_nodes;
		adj_list = new list<int>[no_of_nodes];
	}

	void connect_edge(int u, int v)
	{
		// connect u to v
		adj_list[u].push_back(v);
		// graph is undirected to connect v to u
		// connect v to u
		adj_list[v].push_back(u);
	}
	// getter function
	int getNum_of_nodes(){ return no_of_nodes;}
	list<int>* getlist() { return adj_list;}
};

int max_black_nodes = -9999999;

void solve(int v,G *g, bool *isColored, char *color_of_node)
{

	// base condition
	if(v > 6)
	{
		int  black_count = 0;
		int node_count = g->getNum_of_nodes();
		for(int i=1; i < node_count; i++)
		{
          if( color_of_node[i] == 'b')
        	  black_count++;
		}
		if( black_count > max_black_nodes)
			max_black_nodes = black_count;

		return;
	}

    // check whether node v ,can be colored with black
     bool can_v_color_with_black = true;
     list<int>::iterator it;
     list<int> *adj = g->getlist();

     for(it = adj[v].begin(); it!= adj[v].end();it++)
     {
    	 if(isColored[*it] && color_of_node[*it] == 'b')
    	 {
    		 can_v_color_with_black = false;
    		 break;
    	 }

     }

     isColored[v] = true; // set v as colored

     if(can_v_color_with_black)
     {
    	 // color node v with black
    	 color_of_node[v] = 'b';
    	 solve(v + 1,g, isColored,color_of_node);
     }

     // color node v with white
     color_of_node[v] = 'w';
     solve(v + 1,g, isColored,color_of_node);

     // back track, reset isColored
     isColored[v] = false;

}

int main() {

	// init graph
	G graph(7);
    graph.connect_edge(1,3);
    graph.connect_edge(1,2);
    graph.connect_edge(2,4);
    graph.connect_edge(2,5);
    graph.connect_edge(3,6);
    graph.connect_edge(3,4);
    graph.connect_edge(4,6);
    graph.connect_edge(6,5);

    //helper data for solving problem
    bool isColored[7];
    char color_of_node[7];

    for(int i=0; i < 7; i++)
    {
    	isColored[i] = false;
    	// make all node with black color
    	color_of_node[i] = 'b';
    }



    solve(1,&graph,isColored,color_of_node);

    cout << "max black node would be " << max_black_nodes << endl;

	return 0;
}

Ref:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=129



Related Contents to follow