第五章图着色问题-白红宇

第五章图着色问题

阅读量：4134 次

发布时间：2019-05-25

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

图着色问题是最著名的NP-完全问题，由此还引出了著名的四色定理，四色猜想还曾是一百年来历史上最难的数学难题之一，当然，我不是学数学的，对这些猜想证明一窍不通，也不感冒，但是，图着色问题作为一道算法题目确是很值得研究的，所以作为一名的大学生程序员的我，把它另作一章是无可厚非的

问题描述自不必多说，对于这个问题，我首先想到的就是用搜索+回溯的思想，一个一个的去试，先拿1种颜色图，不行再加一种，等等，代码先贴上

#include 
        
         #include 
         
          using namespace std;#define N 8//表示一张图int g[][N]={	{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,1,0}};//标记的颜色int color[N];//检查是否有邻居标记过同一种颜色int ok(int t){	for(int i=0;i
          
           =N)return true;	for(int i=1;i<=m;i++){		color[t]=i;		if(ok(t)&&traceback(t+1,m))return true;		color[t]=0;	}	return false;}int main(){#ifndef wangchuan	freopen("C:\\in.txt","r",stdin);#endif // !wangchuan		memset(color,0,sizeof(color));			for(int j=1;j<=4;j++){		if(traceback(0,j)){			for(int i=0;i

还有一种Welch Powell法，实质上是一种贪心策略

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

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

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

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

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

//图着色问题//WelchPowell法#include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 8//表示一张图int g[][N]={	{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,1,0}};struct node{	int color;//标记的颜色	int degree;//节点的度数（出度或入度）	int index;//因为要排序，所以先要记录节点所在位置	bool operator<(node &t){		return degree>t.degree;	}}Node[N];void WelchPowell(){    sort(Node,Node+N);	int k = 0;//K 代表第几种颜色	while (true) {		k++;		int i;		for (i = 0; i < N; i++){//先找到第一个未着色的节点			if (Node[i].color == 0) {				Node[i].color = k;				break;			}		}		if (i == N)//循环退出的条件,所有节点都已着色			break;		//再把所有不和该节点相邻的节点着相同的颜色		for(int j=0; j

还有一种简单的贪心算法，先拿一种颜色标记尽量多的点，如果还有点没标，再拿另一种颜色标记，如此反复

//图着色问题//贪心法#include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 8//表示一张图int g[][N]={	{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,1,0}};int color[N];//检查是否有邻居标记过颜色kint ok(int t,int k){	for(int i=0;i

当然还有更加高级的蚁群算法，但是不会写实现代码，等会写的时候再贴上吧

王川

2014/02/17

转载地址：http://ucvvi.baihongyu.com/

你可能感兴趣的文章