圖著色問題（Graph , GCP） 又稱著色問題，是最著名的NP-完全問題之一。道路著色問題（Road ）是圖論中最著名的猜想之一。給定一個無向圖G=（V, E），其中V為頂點集合，E為邊集合，圖著色問題即為將V分為K個顏色組，每個組形成一個獨立集回溯法 圖的m著色問題，即其中沒有相鄰的頂點。其優化版本是希望獲得最小的K值。
解此問題我用的是回溯法.
所謂回溯法，本質其實就是一種蠻力法，只是通過一定的方法可以使得蠻力法中的一些基本情況可以提前排除從而提高蠻力算法效率，回溯可以理解為排除這些不滿足條件的基本情況的過程。
①初始化顏色總數為無窮多種。
②每次從點集中選擇一個頂點并從第一種顏色開始嘗試對其進行著色；
③如果著色不沖突，則繼續通過相同的方式處理點集中的下一個頂點；如果著色沖突，則說明該種著色方法行不通，退回到上一個結點，將上一個結點的著色改為當前著色的下一種顏色。
④重復上述過程，直到所有的頂點都著色為止，此時確定了一個可行解。如果可行解的顏色數少于當前顏色總數，則將顏色總數更新為可行解的顏色數。
⑤得到一個可行解后進行回溯，退回到上一個著色顏色序號小于當前顏色總數的結點上，將其著色改為下一種，并進行如上所示的推理過程。
⑥當存在一個結點沒有顏色可以著色時，算法停止。當前最優解即全局最優解。
代碼附下.
#include
#include
using namespace std;
const int N = 15;
int n, m, a, b;
int color[N], puted[N];
vector G[N];
bool check(int c)
{
for (int i = 0; i < G[c].size(); i ++ )
if(color[c] == color[G[c][i]]) return false;
return true;
}
bool dfs(int cur, int k)
{
if(cur > n)
{
printf("染色成功\n\n");
printf("最少需要%d種顏色\n\n", k);
printf("接下來分別是每個點染上的顏色\n\n");
for(int i = 1; i <= n; i ++ )
{
printf("第%d個點的顏色是%d ", i, color[i]);
if (i % 5 == 0) printf("\n");
}
printf("\n\n方案輸出完畢");
printf("\n");
return true ;
}
if (!puted[k]) printf("正在嘗試能否用%d種顏色為圖染色\n", k), puted[k] = true;
printf("目前正在給點%d染色\n", cur);
for(int clr = 1; clr <= k; clr ++ )
{
color[cur] = clr;
if(check(cur)) { printf("點%d成功染上第%d鐘顏色\n\n", cur, clr); return dfs(cur + 1, k); }
else printf("對于%d點染第%d種顏色出現沖突\n\n", cur, clr);
color[cur] = 0;
}
}
int main()
{
printf("輸入點數n, 邊數m\n");
cin >> n >> m;
printf("輸入%d條無向邊, 每行兩個整數a,b，表示a和b之間有一條無向邊\n\n",m);
while (m -- )
{
scanf("%d%d", &a, &b);
G[a].push_back(b), G[b].push_back(a);
}
for (int i = 1; i <= n; i ++ )
if (!dfs(1, i)) printf("不可以用第%d種顏色為圖染色\n\n", i);
else return 0;
return 0;
} 總結
經過這次課程設計實驗，我體會到只有保持耐心，堅持到底才有可能做好事情。這次課程設計加強了我動手解決問題的能力，鞏固和加深了對數據結構的理解回溯法 圖的m著色問題，提高了綜合運用課程知識的能力，培養了獨立思考、深入研究、分析問題和解決問題的能力。
同時，我也明白了將理論知識與實際相結合的重要性，只有理論知識遠遠不夠，因為在實際設計中還是會遇到不少問題，這次實驗使我發現了自己很多知識漏洞，這對我今后的學習來說是一次非常寶貴的體驗。