用c++写一个顶点着色问题

以下是一个简单的顶点着色问题的实现，其中使用了邻接矩阵表示图，使用了贪心算法进行着色。假设每个顶点的初始颜色都为0，0表示未着色。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

// 初始化图
void init(Graph *g, int vertex_num) {
    int i, j;
    g->vertex_num = vertex_num;
    g->edge_num = 0;
    for (i = 0; i < g->vertex_num; i++) {
        g->vertex[i] = 0;
        for (j = 0; j < g->vertex_num; j++) {
            g->edges[i][j] = 0;
        }
    }
}

// 添加边
void add_edge(Graph *g, int i, int j) {
    if (i >= 0 && i < g->vertex_num && j >= 0 && j < g->vertex_num) {
        g->edges[i][j] = 1;
        g->edges[j][i] = 1;
        g->edge_num++;
    }
}

// 找到一个未着色的顶点
int find_uncolor_vertex(Graph g) {
    int i;
    for (i = 0; i < g.vertex_num; i++) {
        if (g.vertex[i] == 0) {
            return i;
        }
    }
    return -1;
}

// 着色
void color(Graph *g) {
    int i, j, k, color;
    for (i = 0; i < g->vertex_num; i++) {
        if (g->vertex[i] == 0) {
            // 找到一个未着色的顶点
            color = 1;
            // 遍历该顶点的所有邻居
            for (j = 0; j < g->vertex_num; j++) {
                if (g->edges[i][j] == 1 && g->vertex[j] == color) {
                    // 如果邻居已经着色，那么该顶点不能使用这种颜色，需要继续尝试下一种颜色
                    color++;
                    j = -1; // 重新从第一个邻居开始遍历
                }
            }
            // 将该顶点着色
            g->vertex[i] = color;
        }
    }
}

// 打印图的信息
void print(Graph g) {
    int i, j;
    printf("Graph information:\n");
    printf("Vertex num: %d\n", g.vertex_num);
    printf("Edge num: %d\n", g.edge_num);
    printf("Adjacency matrix:\n");
    for (i = 0; i < g.vertex_num; i++) {
        for (j = 0; j < g.vertex_num; j++) {
            printf("%d ", g.edges[i][j]);
        }
        printf("\n");
    }
    printf("Vertex colors:\n");
    for (i = 0; i < g.vertex_num; i++) {
        printf("%d ", g.vertex[i]);
    }
    printf("\n");
}

int main() {
    Graph g;
    int vertex_num, edge_num, i, j;
    printf("Please input the number of vertices and edges:\n");
    scanf("%d%d", &vertex_num, &edge_num);
    init(&g, vertex_num);
    printf("Please input the edges:\n");
    for (k = 0; k < edge_num; k++) {
        scanf("%d%d", &i, &j);
        add_edge(&g, i, j);
    }
    color(&g);
    print(g);
    return 0;
}