ͼ

out< "please input the number of the nodes"<<endl cin>>nodesNum cout<<"pl

//图的着色问题.参见算法基础和笔记
#include<iostream>
#include<cstdlib>      //c++标准程序库里p582,这个文件包括div函数可以求商(quotient)和余数(remainder)  
                       //n.残余, 剩余物, 其他的人, [数]余数v.廉价出售adj.剩余的, 出售剩书的)
                       //该函数返回div_t结构体,这个结构体包括quot和rem
using namespace std;

bool Graph[101][101];  //经过编程验证,全局数组默认赋值为0
int X[101];            //解向量，存放颜色
const int ColorNum =3;  //颜色数目
const int NodeNum = 5;  //结点的个数 


bool check(int k)
{
	//对第k个结点进行检验
	int i;
	for( i = 1;i< k;i++)
	{
		if(Graph[i][k] && X[i] == X[k])
			return false;
	}
	return true;
}

void show_result()
{
	int i;
	cout<<endl<<"---------"<<endl;
	for( i = 1;i <= NodeNum;i++)
	{
     cout<<X[i]<<"       ";
	}
}
void select_color(int k)
{
	//给第k个结点选择颜色
	int i;
	for(i=1;i <= ColorNum; i++)
	{
		X[k] = i;
		if(check(k)) //如果X[k]=i符合规则那么做下列事情，否则x[K]=i+1进入下次循环
		{
			if( k == NodeNum)
			{
				show_result();
			}
			else
				select_color( k+1);

		}
	}
}

void main()
{
	//算法基础p173页的G2图（2，4加条边）
	Graph[1][1]=0; Graph[1][2]=1;  Graph[1][3]=0; Graph[1][4]=1;  Graph[1][5]=1;
	Graph[2][1]=1; Graph[2][2]=0;  Graph[2][3]=1; Graph[2][4]=1;  Graph[2][5]=1;
	Graph[3][1]=0; Graph[3][2]=1;  Graph[3][3]=0; Graph[3][4]=1;  Graph[3][5]=0;
	Graph[4][1]=1; Graph[4][2]=1;  Graph[4][3]=1; Graph[4][4]=0;  Graph[4][5]=0;
	Graph[5][1]=1; Graph[5][2]=1;  Graph[5][3]=0; Graph[5][4]=0;  Graph[5][5]=0;
    select_color(1);
	cout<<endl;
}