mcolor.cpp

这个代码包括求图的最大生成树和Ｍ着色问题．

#include "graph_matrix.h"
#include <vector>

using namespace std;
//--------------private data--------------------------
static vector<int> vcolor;
static int colors;
//--------------private methods-----------------------
static int _mcolor(int n,const  mgraph &g);
static int _get_next_color(int n,const  mgraph &g);
static int _print_color();

int mcolor(int m,const mgraph &g) /* Given a graph G and m colours, colour those nodes of G */
{	
	vcolor.resize(g.size);
	for(int i=0; i<g.size; i++){
		vcolor[i] = 0;
	}
	colors = m;
	return _mcolor(0,g);
}

//--------------private methods-----------------------
static int _mcolor(int n, const mgraph &g)
{
	while(1){
		if(_get_next_color(n,g) == ERROR)
			return ERROR;
		if(n == g.size-1){
			_print_color();
			return OK;
		} else {
			_mcolor(n+1,g);
		}
	}
	return OK;
}
static int _get_next_color(int n, const mgraph &g)
{
	bool flag = false;
	int i;
	while(1){
		vcolor[n] = (vcolor[n] + 1) % (colors + 1);
		if(vcolor[n] == 0){ // no color
			return ERROR;
		}else{
			for(i=0; i<g.size; i++){
				if(i != n && g.edgematrix[i * g.size + n] != MAX_DIS && vcolor[i] == vcolor[n]){
					flag = true;
					break;
				}
			}
		}
		if(flag == false){
			return OK;
		}
		flag = false;
	}
	return OK;
}
static int _print_color()
{
	printf("\nfind a color sollution\n");
	printf("[color] -> [vertex]\n");
	for(int i=0; i<vcolor.size(); i++){
		printf("[%d]->[%d]\n",vcolor[i],i);
	}
	return OK;
}