用c++编写程序，实现输入图G，基于韦尔奇·鲍威尔法对图G的结点进行着色，输出对应的一个正常着色

好的，下面是具体的C++程序实现，希望能对你有所帮助：

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

const int MAXN = 1000;
int n, m;
vector<int> G[MAXN];
int color[MAXN];

enum Color {RED, GREEN, BLUE}; // 枚举结点颜色

struct Node {
    int id;
    int degree; // 结点度数
    bool operator < (const Node& other) const {
        return degree < other.degree; // 结点按度数从小到大排序
    }
};

void welsh_powell() {
    priority_queue<Node> q;
    for(int i=0; i<n; i++) {
        Node node = {i, G[i].size()};
        q.push(node);
    }
    while(!q.empty()) {
        int u = q.top().id;
        q.pop();
        bool used[3] = {false, false, false}; // 记录相邻结点的颜色
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i];
            if(color[v] != -1) {
                used[color[v]] = true;
            }
        }
        for(int i=0; i<3; i++) { // 依次给结点赋颜色
            if(!used[i]) {
                color[u] = i;
                break;
            }
        }
    }
}

void print_color() {
    for(int i=0; i<n; i++) {
        cout << "Node " << i << " : ";
        if(color[i] == RED) {
            cout << "RED" << endl;
        } else if(color[i] == GREEN) {
            cout << "GREEN" << endl;
        } else if(color[i] == BLUE) {
            cout << "BLUE" << endl;
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(color, -1, sizeof(color)); // 初始化结点颜色为-1
    welsh_powell();
    print_color();
    return 0;
}

该程序首先定义了一个枚举类型Color，表示结点的颜色。接着定义了一个Node结构体，包括结点编号和度数，为了实现韦尔奇·鲍威尔法的排序功能，重载了小于号运算符。然后实现了韦尔奇·鲍威尔法算法，主要是通过优先队列来实现结点的排序和贪心思想来实现结点的着色。最后输出着色结果。

希望这个程序对你有所帮助，如果你有什么疑问或者需要进一步的解释，请随时提出。