图的着色问题回溯法C++

图的着色问题可以使用回溯法（backtracking）解决，具体步骤如下：

1. 初始化图的邻接矩阵和颜色数组。
2. 从第一个顶点开始，依次对每个顶点进行着色。
3. 对于当前顶点，从1到k（k为颜色总数）遍历所有可能的颜色，判断该颜色是否可以使用。如果可以使用，则将该颜色赋给该顶点，并继续递归处理下一个顶点；否则尝试下一个颜色。
4. 如果所有颜色都尝试过了，仍然无法为该顶点找到合适的颜色，则回溯到上一个顶点，重新尝试为上一个顶点选择颜色。
5. 如果所有顶点都已经着色完成，则输出着色方案。

下面是C++代码实现：

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1005; // 最大顶点数
int n, m; // n为顶点数，m为边数
int g[MAXN][MAXN]; // 邻接矩阵
int color[MAXN]; // 每个顶点的颜色
int k; // 颜色总数

bool check(int u, int c) // 判断是否可以给顶点u涂上颜色c
{
    for(int i=1; i<=n; i++)
        if(g[u][i] && color[i] == c) // 如果顶点i与顶点u有连边且颜色相同
            return false;
    return true;
}

void dfs(int u)
{
    if(u > n) // 所有顶点都已经着色完成
    {
        // 输出着色方案
        for(int i=1; i<=n; i++)
            cout << color[i] << " ";
        cout << endl;
        return;
    }
    for(int i=1; i<=k; i++) // 枚举所有可能的颜色
    {
        if(check(u, i)) // 如果可以使用颜色i
        {
            color[u] = i; // 给顶点u涂上颜色i
            dfs(u+1); // 递归处理下一个顶点
            color[u] = 0; // 回溯
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    memset(g, 0, sizeof(g)); // 初始化邻接矩阵
    memset(color, 0, sizeof(color)); // 初始化颜色数组
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 1; // 无向图，所以要赋值两次
    }
    dfs(1); // 从第一个顶点开始着色
    return 0;
}

该算法时间复杂度较高，为O(k^n)，其中k为颜色总数，n为顶点数。因此，该算法只适用于顶点数较小的图。