无向图着色问题贪心算法c++

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

#define MAXV 100 // 最大顶点数

int V; // 顶点数
int color[MAXV]; // 顶点颜色
int adj[MAXV][MAXV]; // 邻接矩阵

// 初始化邻接矩阵
void init_adj() {
int i, j;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
adj[i][j] = 0;
}
}
}

// 添加边
void add_edge(int u, int v) {
adj[u][v] = adj[v][u] = 1;
}

// 贪心着色算法
void greedy_coloring() {
int i, j;
int c; // 颜色编号
int used[MAXV]; // 记录已经使用的颜色
for (i = 0; i < V; i++) {
color[i] = -1; // 初始化颜色
}
color[0] = 0; // 第一个顶点着色为0
for (i = 1; i < V; i++) {
for (j = 0; j < V; j++) {
used[j] = 0; // 初始化已使用颜色
}
// 遍历i的邻接点
for (j = 0; j < V; j++) {
if (adj[i][j] && color[j] != -1) {
used[color[j]] = 1;
}
}
c = 0;
// 选择未使用的最小颜色
while (used[c]) {
c++;
}
color[i] = c;
}
}

int main() {
int i, j;
printf("请输入顶点数：");
scanf("%d", &V);
init_adj();
printf("请输入边（-1 -1 结束）：");
while (1) {
int u, v;
scanf("%d%d", &u, &v);
if (u == -1 && v == -1) {
break;
}
add_edge(u, v);
}
greedy_coloring();
printf("着色结果：");
for (i = 0; i < V; i++) {
printf("%d ", color[i]);
}
printf("\n");
return 0;
}