首页 > 专题系列 > 经典问题 > 贪心算法求解-图的m着色问题
2014
02-15

贪心算法求解-图的m着色问题

图的m色判定问题: 给定无向连通图Gm种颜色。用这些颜色为图G的各顶点着色.问是否存在着色方法,使得G中任2邻接点有不同颜色。

图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。

若图G是可平面图,则它的色数不超过4色(4色定理).

4色定理的应用:在一个平面或球面上的任何地图能够只用4种

颜色来着色使得相邻的国家在地图上着有不同颜色

任意图的着色

 

Welch Powell

 

a).将G的结点按照度数递减的次序排列.

b).用第一种颜色对第一个结点着色,并按照结点排列的次序 

   对与前面着色点不邻接的每一点着以相同颜色.

c).用第二种颜色对尚未着色的点重复步骤b).用第三种颜色

   继续这种作法, 直到所有点着色完为止.

 

#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespacestd;

int map[10][10];//邻接矩阵

typedef struct Node{ //定义节点结构体
   int index; //编号
   int degree; //度
   int color; //改节点的颜色
} Node;

Node nodes[10];

bool com(Node node1,Node node2) { //按度从高到低排序
   return node1.degree > node2.degree;
}

bool com2(Node node1,Node node2) { //按度从高到低排序
   return node1.index < node2.index;
}

int main() {
   ifstream read;
   read.open("map.data");//map.data是存放数据的文件名
   int m, n;
   while (read >> m>> n) {
      for (int i = 0; i < m; i++) {//读入数据
         int degree = 0;
         for (int j = 0; j < n; j++) {
            read>> map[i][j];
            if (map[i][j])
                degree++;
         }
         nodes[i].index = i;
         nodes[i].degree = degree;
         nodes[i].color = 0;
      }

      //排序
      sort(nodes,nodes + m, com);
      int k = 0;//K 代表第几种颜色
      while (true) {
         k++;
         int i;
         for (i = 0; i < m; i++){//先找到第一个未着色的节点
            if (nodes[i].color == 0) {
                nodes[i].color = k;
                break;
            }
         }
         if (i == m)//循环退出的条件,所有节点都已着色
            break;
         //再把所有不和该节点相邻的节点着相同的颜色
         for(int j=0; j<m; j++){
            if(nodes[j].color ==0 &&map[nodes[i].index][nodes[j].index] == 0
                   &&i!=j)
                nodes[j].color = k;
         }
      }

      //输出结果:
      sort(nodes,nodes + m, com2);
	cout << "共需要" << k-1 << "种颜色" << endl;
      for (int i = 0; i < m; i++)
         cout<< "节点:"<<nodes[i].index <<":着色" << nodes[i].color <<endl;
      return 0;
   }
}

 

测试数据(map.data):

8 8

0 1 1 1 0 0 1 0

1 0 1 1 1 0 0 0

1 1 0 0 1 1 0 0

1 1 0 0 1 0 1 0

0 1 1 1 0 1 1 1

0 0 1 0 1 0 0 1

1 0 1 1 1 0 0 1

0 0 0 0 1 1 10

即:

 

 

 

运行结果;

共需要3种颜色

 

节点:1:着色1

节点:2:着色2

节点:3:着色3

节点:4:着色3

节点:5:着色1

节点:6:着色2

节点:7:着色2

节点:8:着色3

ACM之家原创,转载请注明出处:http://www.acmerblog.com/article-greed-4292.html


  1. 8 80 1 1 0 0 0 0 01 0 1 0 0 0 0 01 1 0 1 0 0 0 00 0 1 0 1 0 0 00 0 0 1 0 1 1 10 0 0 0 1 0 0 00 0 0 0 1 0 0 00 0 0 0 1 0 0 0該圖應該有三種顏色才對

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  4. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的