/*  Name: 圖的m著色問(wèn)題  Copyright:   Author: 巧若拙   Date: 07-03-17 08:21  Description:   問(wèn)題描述：給定無(wú)向連通圖 G 和 m 種不同的顏色。用這些顏色為圖 G 和各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使得圖 G 中每條邊的兩個(gè)頂點(diǎn)著不同的顏色。這個(gè)問(wèn)題是圖的 m 可著色判定問(wèn)題。若一個(gè)圖最少需要 m 種顏色才能使圖中的每條邊連接的兩個(gè)頂點(diǎn)著不同的顏色，則稱(chēng)這個(gè)數(shù) m 為該圖的色數(shù)。求一個(gè)圖的色數(shù) m 的問(wèn)題稱(chēng)為圖的 m 可著色優(yōu)化問(wèn)題。子集樹(shù)，O(n*(m^n))時(shí)間復(fù)雜度四色問(wèn)題是m圖著色問(wèn)題的一個(gè)特例，根據(jù)四色原理，證明平面或球面上的任何地圖的所有區(qū)域都至多可用四種、顏色來(lái)著色，并使任何兩個(gè)有一段公共邊界的相鄰區(qū)域沒(méi)有相同的顏色。這個(gè)問(wèn)題可轉(zhuǎn)換成對(duì)一平面圖的４－著色判定問(wèn)題(平面圖是一個(gè)能畫(huà)于平面上而邊無(wú)任何交叉的圖)。將地圖的每個(gè)區(qū)域變成一個(gè)結(jié)點(diǎn)，若兩個(gè)區(qū)域相鄰，則相應(yīng)的結(jié)點(diǎn)用一條邊連接起來(lái)。多年來(lái)，雖然已證明用5種顏色足以對(duì)任一幅地圖著色，但是一直找不到一定要求多于4種顏色的地圖。直到1976年這個(gè)問(wèn)題才由愛(ài)普爾，黑肯和考西利用電子計(jì)算機(jī)的幫助得以解決。他們證明了4種顏色足以對(duì)任何地圖著色。在這一節(jié)，不是只考慮那些由地圖產(chǎn)生出來(lái)的圖，而是所有的圖。討論在至多使用m種顏色的情況下，可對(duì)一給定的圖著色的所有不同方法。 分析：可以通過(guò)回溯的方法，不斷的為每一個(gè)節(jié)點(diǎn)著色，在前面n-1個(gè)節(jié)點(diǎn)都合法的著色之后，開(kāi)始對(duì)第n個(gè)節(jié)點(diǎn)進(jìn)行著色，這時(shí)候枚舉可用的m個(gè)顏色，通過(guò)和第n個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的顏色，來(lái)判斷這個(gè)顏色是否合法，如果找到那么一種顏色使得第n個(gè)節(jié)點(diǎn)能夠著色，那么說(shuō)明m種顏色的方案是可行的。*/#include<iostream>#include<string>using namespace std;const int N = 5; //圖中節(jié)點(diǎn)的個(gè)數(shù)const int m = 3; //顏色的種int map[N][N]={0,1,1,0,1,               1,0,1,1,0,               1,1,0,1,1,               0,1,1,0,1,               1,0,1,1,0};//鄰接矩陣int c[N];//記錄著的是哪種顏色int sum = 0;//保存可以著色的方案數(shù)bool OK(int t);//檢查當(dāng)前頂點(diǎn)著色是否合法 void Backtrace(int t); //遞歸回溯 void Backtrace_2(); //非遞歸回溯 int main() {   Backtrace(0);  // Backtrace_2();      system("pause");   return 0;}bool OK(int t)//檢查當(dāng)前頂點(diǎn)著色是否合法 {    for(int i=0; i<t; i++)    {        if(map[i][t] == 1 && c[i] == c[t])      			return false;           }    return true;}void Backtrace(int t) //遞歸回溯 {    if(t == N)    {        sum++;        cout << "方案" << sum << ": ";        for(int i=0; i<N; i++)        {            cout << c[i] << " ";        }        cout << endl;    }    else    {        for(int i=1; i<=m; i++)        {			c[t] = i;            if(OK(t))				Backtrace(t+1);        }      //  c[t] = 0;   //顏色還原并回溯（由于c[t]每次都從1開(kāi)始取值，故顏色無(wú)需還原）     }}void Backtrace_2() //非遞歸回溯 {	int t = 0; //第一個(gè)頂點(diǎn)入棧		while(t >= 0)	{		while(c[t]++ < m)//c[t]默認(rèn)初始化為0 		{			if (OK(t)) //c[t]顏色可行才進(jìn)入下一步 			{				if(t == N-1)				{					sum++;					cout << "方案" << sum << ": ";					for(int i=0; i<N; i++)					{						cout << c[i] << " ";					}					cout << endl;				}				else				{					t++;				}			}		}		c[t--] = 0; //顏色還原并回溯	}}