回溯法——圖着色問題

圖着色問題

“四色問題”一直是數學方面一個重要且困難的問題，直到計算機的發明才得以側面證明，如何求一個圖的着色色數，可以通過回溯法來解決。

問題描述

已知一個圖G和m種顔色，在隻準使用這m種顔色對G的結點着色的情況下，是否能使圖中任何相鄰的兩個結點都具有不同的顔色呢？這個問題稱為m-着色判定問題。可對圖G着色的最小正整數m，稱為圖G的色數。

分析設計

圖的表示我們采用二維數組鄰接矩陣的形式存儲。顔色我們可以使用正整數1、2、3……m的形式表示，通過一位數組x[n]來記錄結點顔色，x[i]表示結點i的顔色為x[i]。

我們可以通過深度周遊的方法周遊每一個結點，顔色也從1開始試，在給每個結點确定顔色時，判斷與它相鄰的結點是否着色沖突：

• 都不沖突，則繼續往下一個結點走；
• 存在沖突，則換一個顔色繼續試；當所有顔色試完均無可行解，則回溯至上一個頂點；
• 當所有頂點都找到了一種顔色解決時，我們就可以說改圖所需色數可能小于等于m。

源代碼

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool> > graph;	//鄰接圖
vector<int> x;					//節點數組
int color;						//顔色種類

//輸出結果
void print(int k) {
	for (int i = 1; i <= k; i++) 
		cout << x[i] << " ";
	cout << endl;
}

//遞歸算法
void MColoring(int k) {
	int j;
	while (1) {
		x[k]++;
		if (x[k] > color)
			return;
		for (j = 1; j <= k - 1; j++) 
			if (graph[k][j] && x[k] == x[j])	//存在沖突
				break;
		if (j == k)
			break;
	}
	if (k == x.size() - 1) {	//找到一種可能
		print(k);
		return;
	}
	else
		MColoring(k + 1);	//遞歸進入下一層
}


int main() {
	int n;
	cout << "輸入圖頂點數：";
	cin >> n;
	vector<vector<bool> >g(n + 1, vector<bool>(n + 1, false));	//鄰接矩陣圖
	cout << "輸入鄰接邊a b：（輸入0結束）" << endl;
	int a, b;
	while (cin >> a && a) {
		cin >> b;
		g[a][b] = true;
		g[b][a] = true;
	}
	graph = g;

	vector<int> t(n + 1, 0);
	x = t;
	x[1] = 1;

	cout << "輸入顔色種類：";
	cin >> color;

	MColoring(1);

	system("pause");
	return 0;
}


/*
1 2
2 3
1 3
1 4
2 4
2 5
3 4
4 5
*/
           

運作結果