基于韦尔奇·鲍威尔法对图着色 含c++代码

期末考试前面的最后一次离散数学编程作业，十分感慨。

一学期的离散数学学习，让我懂得了不能说是整个离散数学的体系吧，也可以说是一点也听不懂了，现在正值6月13号这么一个神圣的日子，我不禁感叹：我真的不想挂科。但是这门折磨的所谓的“专业课”也就到此为止了，或余实不合科研之路，只得目光短浅于两三前后端之琐事。故人各有志，非众生皆可忍导师压榨之苦、论文枯竭之苦，愚且鼠目寸光之辈哉，且浮于浅显之处乎！遂钟写此篇，抒己浅志，且造福于众生也。

---

代码如下：（望君付师作业时稍加改动，不至连坐之刑也）

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

class Node {
private:
    int degree;
    int color = -1;
    int number;
    static int maxColor;
    vector<int> connected;
public:
    explicit Node(int degree = 0, int number = 0) : degree(degree), number(number) {}
    ~Node() = default;
    int getDegree() const;
    int getColor() const;
    int getNumber() const;
    void setDegree(const int& d);
    void setColor(const int& c);
    void setNumber(const int& n);
    void pushNode(const int& n);
    static void setMaxColor(const int& max);
    static int getMaxColor();
    bool find(Node* node);
    bool operator>=(const Node& node) const;
};

int Node::maxColor = -1;

int Node::getDegree() const {
    return degree;
}

int Node::getNumber() const {
    return number;
}

int Node::getColor() const {
    return color;
}

void Node::setColor(const int &c) {
    color = c;
}

void Node::setNumber(const int &n) {
    number = n;
}

void Node::setDegree(const int &d) {
    degree = d;
}

void Node::pushNode(const int &n) {
    connected.push_back(n);
    degree++;
}

bool Node::find(Node *node) {
    for (auto &item: connected) {
        if (item == node->number) {
            return true;
        }
    }
    return false;
}

void Node::setMaxColor(const int &max) {
    if (maxColor < max) {
        maxColor = max;
    }
}

int Node::getMaxColor() {
    return maxColor;
}

bool Node::operator>=(const Node& node) const {
    return degree >= node.degree;
}

bool cmp(Node* a, Node* b) {
    return a->getDegree() > b->getDegree();
}

class Graph{
private:
    vector<Node*> nodes;
public:
    Graph() = default;
    ~Graph() = default;
    void init(vector<vector<int>>& matrix);
    bool isColored();
    void showColor();
    void startColor();
};

void Graph::init(vector<vector<int>> &matrix) {
    for (int i = 0; i < matrix.size(); i++) {
        auto node = new Node(0, i + 1);
        for (int j = 0; j < matrix[i].size(); j++) {
            if (i == j) {
                continue;
            } else if (matrix[i][j] == 1) {
                node->pushNode(j + 1);
            }
        }
        nodes.push_back(node);
    }
    sort(nodes.begin(), nodes.end(), cmp);
    nodes[0]->setColor(0);
    Node::setMaxColor(0);
}

bool Graph::isColored() {
    for (const auto &item: nodes) {
        if (item->getColor() == -1) {
            return false;
        }
    }
    return true;
}

void Graph::showColor() {
    cout << "--------------------------" << endl;
    for (int i = 0; i < nodes.size(); i++) {
        if (i != nodes.size() - 1) {
            cout << "v" << i + 1 << ":" << nodes[i]->getColor() << ",";
        } else {
            cout << "v" << i + 1 << ":" << nodes[i]->getColor();
        }
    }
    cout << endl;
    cout << "--------------------------" << endl;
}

void Graph::startColor() {
    for (int i = 1; i < nodes.size(); i++) {
        int check = 0;
        for (int j = 0; j < i; j++) {
            if (nodes[i]->find(nodes[j])) {
                continue;
            } else {
                nodes[i]->setColor(nodes[j]->getColor());
                check = 1;
                break;
            }
        }
        if (check == 0) {
            nodes[i]->setColor(Node::getMaxColor() + 1);
            Node::setMaxColor(nodes[i]->getColor());
        }
    }
}

int main() {
    vector<vector<int>> matrix;
    int n;
    cout << "输入节点个数" << endl;
    cin >> n;
    cout << "输入邻接矩阵" << endl;
    cout << "  ";
    for (int i = 0; i < n; i++) {
        cout << i + 1 << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        cout << i + 1 << " ";
        for (int j = 0; j < n; j++) {
            int value;
            cin >> value;
            temp.push_back(value);
        }
        matrix.push_back(temp);
    }
    Graph p;
    p.init(matrix);
    p.startColor();
    p.showColor();
    return 0;
}

---

愚尚且不及佬也，若有不慎之处，恳请指正于评论区。