c语言写回溯算法图着色问题

回溯算法是一种经典的求解图着色问题的方法。下面是一个简单的C语言实现：

#include <stdio.h>
#include <stdbool.h>

#define N 5 // 图中的节点数
#define M 4 // 颜色数

int graph[N][N] = { // 图的邻接矩阵
    {0, 1, 1, 1, 0},
    {1, 0, 1, 0, 1},
    {1, 1, 0, 1, 1},
    {1, 0, 1, 0, 1},
    {0, 1, 1, 1, 0}
};

int colors[N] = {0}; // 每个节点的颜色

bool is_valid(int node, int color) {
    for (int i = 0; i < N; i++) {
        if (graph[node][i] && color == colors[i]) {
            return false; // 如果相邻节点已被涂上该颜色，则不合法
        }
    }
    return true;
}

bool graph_coloring(int node) {
    if (node == N) { // 如果所有节点的颜色都已确定，则返回true
        return true;
    }
    for (int i = 0; i < M; i++) { // 尝试每一种颜色
        if (is_valid(node, i)) { // 如果当前颜色合法
            colors[node] = i; // 将当前节点涂上该颜色
            if (graph_coloring(node + 1)) { // 递归求解下一个节点
                return true; // 如果下一个节点已求解，则返回true
            }
            colors[node] = 0; // 如果下一个节点无解，则回溯
        }
    }
    return false; // 如果所有颜色都尝试过，仍然无法得到解，则返回false
}

int main() {
    if (graph_coloring(0)) {
        printf("The graph can be colored as follows:\n");
        for (int i = 0; i < N; i++) {
            printf("Node %d: color %d\n", i, colors[i]);
        }
    } else {
        printf("No solution found.\n");
    }
    return 0;
}

在上面的代码中，我们定义了一个5个节点的图的邻接矩阵，并假设有4种颜色可选。`is_valid`函数用于判断某个节点是否可以涂上某种颜色。`graph_coloring`函数则是回溯求解的核心，它从第一个节点开始，逐个尝试每种颜色，如果当前颜色合法，则递归求解下一个节点；如果下一个节点无解，则回溯到当前节点，尝试下一种颜色。如果所有颜色都尝试过，仍然无法得到解，则返回false。最后，如果求解成功，则输出每个节点的颜色。