贪心算法无向连通图图着色问题 的c++ 代码

贪心算法可以用于解决无向连通图的最小颜色着色问题，也称为Kosaraju-Shiloach算法。这个算法不是简单地给每个顶点分配最少的颜色，而是采用一种策略，确保相邻节点的颜色不同。以下是基于Dijkstra's Algorithm原理的一个简化版的C++代码：

#include <iostream>
#include <vector>
#include <queue>

// 定义图的邻接表结构
struct Graph {
    std::vector<std::vector<int>> adj;
};

// 颜色数组
std::vector<int> color;

// 检查颜色是否冲突
bool isSafe(int u, int c) {
    for (int v : adj[u]) {
        if (color[v] == c)
            return false;
    }
    return true;
}

// 贪心着色函数
void greedyColoring(Graph &g, int n) {
    std::queue<int> q;
    // 对于每个顶点，将其添加到队列并初始化其颜色
    for (int i = 0; i < n; ++i) {
        if (!color[i])
            q.push(i), color[i] = 1;
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 尝试给u的所有邻居分配当前未使用的最大颜色
        for (int v : g.adj[u]) {
            if (!isSafe(v, color[u])) {
                continue; // 如果冲突，尝试下一个颜色
            }
            color[v] = color[u] + 1;
            if (!color[v])
                color[v] = 2; // 如果新的颜色是1，则加1
            q.push(v); // 更新队列
        }
    }
}

int main() {
    // 初始化一个简单的无向图示例
    Graph g = {{1, 2}, {2, 3}, {4, 5}, {5, 6}};
    int n = g.adj.size(); // 图的顶点数

    color.resize(n, 0);
    greedyColoring(g, n);

    // 打印每个顶点的颜色
    for (int i = 0; i < n; ++i) {
        std::cout << "Vertex " << i << " has color " << color[i] << '\n';
    }

    return 0;
}

这个代码首先创建了一个邻接表表示无向图，然后对每个顶点应用贪心策略进行着色。注意这只是一个简化版本，实际应用可能需要处理更复杂的情况。