用c语言编写一个程序。用贪心法实现求无向连通图G=(V, E)的最小色数 k，使得用 k 种颜色对 G 中的顶点着色，使任意两个相邻顶点着不同颜色。并输出最小最小着色数k以及各个顶点的着色。给出完整代码，方便我直接运行

在C语言中，我们可以使用深度优先搜索（DFS）结合贪心策略来解决这个问题。因为贪心算法并不能保证找到全局最优解，但它可以提供一种相对简单的近似方法。这里我们将创建一个函数，用于检查最小颜色数并为每个顶点分配颜色。请注意，这种方法假设图已经输入为邻接矩阵，且边的权重并不重要，只关注是否相连。

#include <stdio.h>
#include <stdbool.h>
#define V 5 // 根据实际图规模调整

// 邻接矩阵表示
int graph[V][V];

// 辅助数组，用于记录已访问节点的颜色
bool color[V];

// 检查给定顶点 v 是否可以用当前未使用的颜色着色
bool canColor(int v, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && color[i] == c) return false;
    }
    return true;
}

// 找到最小着色数并染色
int minColoring() {
    int k = 1; // 初始颜色数为1
    while (true) {
        bool ok = true; // 是否能找到下一个颜色
        for (int v = 0; v < V; ++v) {
            if (!color[v]) {
                for (int c = 0; c < k; ++c) {
                    if (canColor(v, c)) {
                        color[v] = c;
                        break;
                    }
                }
                if (color[v] == 0) { // 如果找不到可用颜色，增加颜色数
                    ok = false;
                    ++k;
                    break;
                }
            }
        }
        if (ok) break;
    }
    return k;
}

// 主函数，读取图并打印结果
void mainProgram() {
    // 请在这里填写如何初始化邻接矩阵graph
    // 例如：for (int i = 0; i < V; i++)
    //       for (int j = 0; j < V; j++)
    //           scanf("%d", &graph[i][j]);

    int k = minColoring();
    printf("Minimum coloring number is %d.\n", k);

    // 打印着色结果
    for (int i = 0; i < V; ++i) {
        if (color[i])
            printf("Vertex %d is colored with color %d.\n", i, color[i]);
        else
            printf("Vertex %d could not be colored.\n", i);
    }
}