注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

伯纳乌の夢

可以挽回么?我们按“ Ctrl+Z”撤销掉吧。对不起啦~~

 
 
 

日志

 
 
 
 

2008年3月14日  

2008-03-14 13:47:17|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

地图着色算法C语言实现[转]
 [ BugEyes 发表于 2005-11-18 11:06:00 ]
 
 
定理:任何平面地图可以使用4种颜色给每个不同的城市着色,而保证相邻的城市着不同的颜色。
       思路:把地图上的每个城市抽象为一个点,并给每个城市编号,,相邻的城市之间用直线连接。据此做出邻接矩阵,若第i个城市与第j个城市相邻,则metro[i][j]=1,否则metro[i][j]=0。
       算法:按照编号从小到大的顺序检查每个城市,对每个城市从1到4使用4种颜色着色,若当前颜色可用(即不与相邻城市颜色相同),则着色;否则测试下一种颜色。
      程序:
#i nclude <stdio.h>
#define N 21

int ok(int metro[N][N],int r_color[N],int current)
{/*测试当前着色方案是否可行*/
   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 main()
{
   int r_color[N]={0};
   int i;
   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}};
   go(metro,r_color,20,1);
   printf("\n");
   for(i=1;i<=20;i++)/*输出着色方案*/
     printf("%3d",r_color[i]);
}

      中午吃饭时,想了一下,把上面程序中的go函数和ok函数合并一下,并且不使用递归,于是写下了下面color函数的代码,main函数不变,但调用方式变为color(metro,r_color,20);请朋友多批评

void color(int metro[N][N],int r_color[N],int sum)
{
   int i,j,k;
   for(i=1;i<=sum;i++)/*检查所有城市*/
     for(j=1;j<=4;j++)/*对每个城市尝试4种颜色的着色方案*/
     {
        r_color[i]=j;/*尝试着色*/
        for(k=1;k<i;k++)/*检查是否与相邻城市颜色相同*/
            if(metro[i][k]==1&&r_color[k]==r_color[i])
               break;/*相同则跳出,此时有k<i,则下面条件不成立,继续尝试下一种颜色*/
        if(k>=i)/*若不相同,则使用当前颜色,并检查下一个城市*/
            break;
     }
}

  评论这张
 
阅读(80)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018