图着色问题代码c++

图着色问题是一个经典的计算机科学问题，通常涉及到给定无向图的颜色分配，使得相邻的节点颜色不同。在C++中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）结合回溯算法来解决此问题。以下是一个简单的例子，展示如何用DFS实现图的K-coloring问题：

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

// 代表一个顶点及其邻接的列表
struct Node {
    int id;
    vector<int> adj; // 邻接顶点的ID
};

bool canColor(Node node[], int k, int color[]); // 判断是否能给当前节点染上颜色
void dfs(Node node[], int color[], bool visited[], int k);

int main() {
    int n, m; // n表示节点数，m表示边的数量
    cin >> n >> m;
    
    Node graph[n]; // 创建n个节点
    for (int i = 0; i < n; ++i) {
        cin >> graph[i].id;
        graph[i].adj.clear();
    }

    // 输入边信息
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u - 1].adj.push_back(v - 1);
        graph[v - 1].adj.push_back(u - 1); // 图是无向的
    }
    
    int colors[n]; // 存储每个节点的颜色
    memset(colors, -1, sizeof(colors)); // 初始化所有颜色为未分配

    dfs(graph, colors, new bool[n], k); // 开始深度优先搜索，k表示最大允许颜色数
    if (!canColor(graph, k, colors)) { // 检查是否有无法着色的情况
        cout << "No coloring with " << k << " colors possible." << endl;
    } else {
        cout << "A valid coloring is possible using " << k << " colors:" << endl;
        for (int i = 0; i < n; ++i) {
            cout << "Node " << graph[i].id << " has color: " << colors[i] + 1 << endl;
        }
    }

    return 0;
}

// 深度优先搜索函数，递归地尝试给节点分配颜色
void dfs(Node node[], int color[], bool visited[], int k) {
    visited[node->id] = true;
    for (int neighbor : node->adj) {
        if (!visited[neighbor]) {
            if (canColor(node, k, color)) { // 如果邻接节点可以用新的颜色
                color[neighbor] = (color[node->id] + 1) % k; // 继续分配新颜色
                dfs(node, color, visited, k); // 对邻接节点进行深度优先搜索
            }
        } else if (color[node->id] == color[neighbor]) { // 如果邻接节点已经有相同的颜色
            return; // 回溯，无法继续着色
        }
    }
}

// 判断是否能给当前节点染上颜色
bool canColor(Node node[], int k, int color[]) {
    for (int neighbor : node->adj) {
        if (color[neighbor] == color[node->id]) { // 邻接节点有相同的颜色
            return false;
        }
    }
    return true;
}