地图着色算法C语言源代码.rar_分布式_地图着色代码_地图着色算法_着色算法_着色问题

地图着色算法C语言源代码[原创] 前面我写了一个地图着色（即四色原理）的C源代码。见http://bugeyes.blog.edu.cn/user1/20989/archives/2005/986232.shtml。 写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处： ＃i nclude <stdio.h> #define N 21 int allcolor[4];/*可用的颜色*/ int ok(int metro[N][N],int r_color[N],int current) {/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/ int j; for(j=1;j<current;j++) if(metro[current][j]==1&&r_color[j]==r_color[current]) return 0; return 1; } void go(int metro[N][N],int r_color[N],int sum,int current) { int i; if(current<=sum) for(i=1;i<=4;i++) { r_color[current]=i; if(ok(metro,r_color,current)) { go(metro,r_color,sum,current+1); return; } } } void color(int metro[N][N],int r_color[N],int sum,int start) { int i,j,k; r_color[start]=allcolor[0]; for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/ if(i==0)/*城市号从1开始编号,故跳过0编号*/ continue; else for(j=0;j<4;j++) { r_color[i]=allcolor[j];/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/ for(k=1;k<i;k++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/ if(metro[i][k]==1&&r_color[k]==r_color[i]) break; if(k>=i) break; } } void main() { int r_color[N]={0}; int t_color[N]={0}; int i; int start;/*着色的起点*/ int metro[N][N]={{0}, {0,1,1,1,1,1,1}, {0,1,1,1,1}, {0,1,1,1,0,0,1}, {0,1,1,0,1,1}, {0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1}, {0,1,0,1,0,1,1,1,1,1}, {0,0,0,0,0,0,1,1,1}, {0,0,0,0,0,0,1,1,1,1,0,0,1}, {0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1}, {0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1}, {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1}, {0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1}, {0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1}, {0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1}, {0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1}, {0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1}, {0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1}, {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}}; allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/ start=1; /* clrscr();*/ printf("\nAll color is:\n"); for(i=0;i<4;i++)/*当前选色顺序*/ printf("%d ",allcolor[i]); go(metro,r_color,20,1); printf("\nFirst method:\n"); for(i=1;i<=20;i++) printf("%3d",r_color[i]); color(metro,t_color,20,start); printf("\nSecond method:\n"); printf("\nAnd the start metro is:%d\n",start); for(i=1;i<=20;i++) printf("%3d",t_color[i]); } 说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。