本文共 3112 字，大约阅读时间需要 10 分钟。

0x00 图着色问题

图着色问题（Graph Coloring Problem, GCP）又称着色问题，是最著名的NP-完全问题之一。

• 图的m可着色判定问题

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。

• 图的m可着色优化问题

若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。

0x01 图的m可着色判定问题

判定问题采用暴力dfs处理，对于当前的节点cur，其前面的节点已经着色过了，判断cur节点可以使用的颜色即可。如何判断cur节点可以使用的颜色呢？遍历所有颜色，判断当前颜色i和cur周围节点的颜色是不是不一样，如果是的话，那么可行；否则，不可行。

#include 
   
    #include 
    
     using namespace std;const int N = 100, M = N * 2;struct Edge {
       int to, next;} edge[M];int head[N], color[N], idx = -1;int n, m, k;// n表示节点个数， m表示颜色个数，k表示数据个数bool res = false;void add(int u, int v) {
       edge[++idx].to = v;    edge[idx].next = head[u];    head[u] = idx;}//判断位置cur是否可以放入颜色ibool check(int cur, int i) {
       for (int j = head[cur]; ~j; j = edge[j].next) {
           int son = edge[j].to;        if (color[son] == i) return false;    }    return true;}void dfs(int cur) {
    //cur从0开始计算    if (cur >= n) {
           res = true;        return;    }    for (int i = 1; i <= m; i++) {
           if (check(cur, i)) {
               color[cur] = i;            dfs(cur + 1);        }    }}
    
   

另外上述代码稍加修改就可以计算方案个数。

#include 
   
    #include 
    
     using namespace std;const int N = 100, M = N * 2;struct Edge {
       int to, next;} edge[M];int head[N], color[N], idx = -1;int n, m, k;int res;void add(int u, int v) {
       edge[++idx].to = v;    edge[idx].next = head[u];    head[u] = idx;}bool check(int cur, int i) {
       for (int j = head[cur]; ~j; j = edge[j].next) {
           int son = edge[j].to;        if (color[son] == i) return false;    }    return true;}void dfs(int cur) {
       if (cur >= n) {
           res++;        return;    }    for (int i = 1; i <= m; i++) {
           if (check(cur, i)) {
               color[cur] = i;            dfs(cur + 1);            color[cur] = 0;        }    }}
    
   

0x02 图的m可着色优化问题

我在论坛上看到如下问题

元素=[1,2,3,4,5,6,7,8,9] 互斥=[(1,4),(2,5),(1,5),(5,6),(7,8),(3,9),(2,8),(4,5)]把元素组成 N 个组, 保证互斥元素不在同一个组里, 并且 N 最小

这个问题实际上就是图的m可着色优化问题。

图的m可着色优化问题首先不难想到通过二分法（加上0x01中的方法）来做，但是这么做的话时间复杂度过高。可以直接采用dfs来处理。（为了处理简单，使用矩阵存储图）

每次判断当前数cur能不能放入之前的集合中，如果不能放入，那么新开辟一个集合；否则，放入即可。那么关键问题就是判定能否放入之前的集合中？将集合中的每个数存储，然后判断当前数cur和这些数是不是互斥即可。

#include 
   
    #include 
    
     using namespace std;const int N = 100;int cnt[N], num[N][N], g[N][N];//cnt表示每个集合中元素个数，num表示第i个集合中的第j个元素是谁，g表示关系图。int n, k;// n表示节点个数，k表示数据个数int res;//判断第i个集合是不是可以放入cur（也就是i中的元素都不和cur互斥）bool check(int cur, int i) {
       for (int j = cnt[i]; j > 0; --j) {
           if (g[num[i][j]][cur]) return false;    }    return true;}//将cur放入第s个集合中void dfs(int cur, int s) {
    //cur从1开始计算    if (s >= res) return;    if (cur > n) {
           res = s;        return ;    }    for (int i = 1; i <= s; i++) {
            if (check(cur, i)) {
               num[i][++cnt[i]] = cur;            dfs(cur + 1, s);            num[i][cnt[i]--] = 0;        }    }    s++;    num[s][++cnt[s]] = cur;    dfs(cur + 1, s);    num[s][cnt[s]--] = 0;}
    
   

reference:

https://baike.baidu.com/item/%E5%9B%BE%E7%9D%80%E8%89%B2%E9%97%AE%E9%A2%98/8928655?fr=aladdin

https://www.cnblogs.com/czsharecode/p/10558732.html

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102563756 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！