图着色问题（graph coloring problem）求无向连通图G=(V, E)的最小色数 k，使得用 k 种颜色对 G 中的顶点着色，使任意两个相邻顶点着不同颜色。的C++算法

图着色问题是经典的问题，通常采用贪心算法来解决。对于无向连通图，一种常见的方法是使用启发式搜索策略，如迭代加深搜索（Iterative Deepening Depth First Search, IDDFS），结合回溯（backtracking）。下面是一个简化的IDDFS算法示例，用于寻找最小色数k：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 颜色枚举
enum Color { UNCOLORED, RED, GREEN, BLUE };

// 边结构
struct Edge {
    int from, to;
};

// 图的表示
class Graph {
private:
    vector<vector<int>> adj; // 邻接表
public:
    Graph(vector<Edge>& edges) {
        adj.resize(edges.size());
        for (Edge edge : edges) {
            adj[edge.from].push_back(edge.to);
            adj[edge.to].push_back(edge.from); // 添加双向边
        }
    }

    // 是否安全着色当前顶点
    bool safe_color(int vertex, int current_color, vector<Color>& colors) {
        for (int neighbor : adj[vertex]) {
            if (current_color == colors[neighbor]) return false;
        }
        return true;
    }

    // 调整颜色并递归遍历邻居
    void dfs(int vertex, vector<Color>& colors, int color, int& depth) {
        colors[vertex] = color;
        queue<int> q;
        q.push(vertex);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (depth >= adj.size()) break; // 到达深度限制，可能是解决方案
            if (safe_color(u, color, colors)) {
                for (int neighbor : adj[u]) {
                    if (colors[neighbor] == UNCOLORED) {
                        dfs(neighbor, colors, (color+1)%4, depth+1); // 四种颜色循环
                    }
                }
            } else {
                colors[vertex] = UNCOLORED; // 回溯到上一层
            }
        }
    }

    // 求解最小色数
    int find_min_color() {
        int min_depth = INT_MAX;
        for (int i = 0; i < 4; ++i) { // 最初尝试四种颜色
            vector<Color> colors(adj.size(), UNCOLORED);
            dfs(0, colors, i, 0);
            if (count(colors.begin(), colors.end(), UNCOLORED) == 0) {
                min_depth = min(min_depth, adj.size()); // 更新最小深度
            }
        }
        return min_depth == INT_MAX ? -1 : min_depth; // 若未找到解决方案，返回-1
    }
};

int main() {
    // 示例图的边输入
    vector<Edge> edges = {{0, 1}, {1, 2}, {2, 3}};
    Graph graph(edges);

    int minK = graph.find_min_color();
    if (minK != -1) {
        cout << "最小着色数k为：" << minK << endl;
    } else {
        cout << "无法着色" << endl;
    }

    return 0;
}

这个代码实现了基本的迭代加深搜索，如果找到一个解决方案，就更新最小深度。如果没有找到满足条件的着色方案，它将返回-1。注意，这个算法可能不是最优的，对于某些复杂的图，可能需要更复杂的算法，例如基于局部搜索优化的启发式方法。