地图着色算法c语言_数据结构C语言四染色定理

A. 数据结构c语言四染色定理

下面是用的c++描述的：涉及到类的有关知识。你不知道的话我可以帮你改为c语言描述。不过需要时间（这个星期之内），我最近比较的忙。反正你加了分，你就慢慢等吧！不好意思，我最近太忙了，没时间给你改。再加点分让别人给你回复吧！
class color{
friend int mcoloring(int,int,int * *);
private:
bool OK(int k);
void Backtrack(int t）；
int n,//图的定点数
m,//可用颜色数
**a,//图的临接矩阵
*x;//当前解
long sum;//当前已找到的可m着色方案数
};
bool color::OK(int k)
{ //检查颜色的可用性
for(int j=1;j<=n;j++)
if((a[k][j]==1)&&(x[j]==x[k]))return false;
return true ;
}
void color::Backtrack(int t)
{
if(t>n){
sum++;
for(int i=1;i<=n;i++)
cout<<x[i]<<" ";
cout<<endl;
}
else for(int i=1;i<=m;i++)
{ x[t]=i;
if(OK(t))Backtrck(t+1);
x[t]=0;
}
}
int mcoloring (int n,int m,int **a）
｛color X;
//初始化
X.n=n;
X.m=m;
X.a=a;
X.sum=0;
int *p=new int [n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete []p;
return X.sum;
}

B. 地图着色问题C/C++

从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。

地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。

写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：

＃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]);
}

说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。

C. c# 地图四染色

很麻烦的算法题，分有点少........

啧，分还是少........算了，给你写个简单的把

using System;
using System.Collections.Generic;

namespace 四色猜想
{
public class FourColor
{
public static void Run(int aeraNumeric)
{
//为了偷懒，没有使用二维矩阵而是直接用了栈，即X的最大相邻数为2即X-1和X+1，实际上2个颜色就够用了....
//实例化栈
Stack<Aera> AeraStack = new Stack<Aera>(aeraNumeric);
//演示算法，使用随机颜色
Random RandomColor = new System.Random();

for (int i = 0; i < aeraNumeric; i++)
{
//初始化Aera并入栈
Aera MyAera = new Aera((i + 1).ToString(), (Publicenum.FourColor)(RandomColor.Next(4)));
//入栈
if (AeraStack.Count == 0)
{
AeraStack.Push(MyAera);
continue;
}
Aera TestAera = AeraStack.Peek();
if (TestAera.AeraColor == MyAera.AeraColor)
{
int j = 0;
while (j < 5)
{
if (j == 4)
{
throw new InvalidOperationException("超出4色范围!");
}
Publicenum.FourColor TestColor = (Publicenum.FourColor)j;
if (TestAera.AeraColor == TestColor)
{
j++;
continue;
}
else
{
MyAera.AeraColor = TestColor;
break;
}

}
}
AeraStack.Push(MyAera);
}

//输出结果
while (AeraStack.Count != 0)
{
Aera OutputAera = AeraStack.Pop();
Console.WriteLine("Name:{0},Color:{1}", OutputAera.AeraName, OutputAera.AeraColor);
}
Console.ReadLine();
}
}

public class Aera
{
public string AeraName { get; set; }
public Publicenum.FourColor AeraColor { get; set; }

public Aera(string aeraName, Publicenum.FourColor aeraColor)
{
AeraName = aeraName;
AeraColor = aeraColor;
}
}

public class Publicenum
{
public enum FourColor
{
A, B, C, D
}
}
}

控制台程序，调用时输入区域个数如 FourColor.Run(73);

D. 地图着色问题源程序C++语言（算法设计与分析）急求

E. C语言编程地图着色

书上有嘛

F. 求我描述的地图填色问题详解(100分,只求详尽)

最少填色数量,这个似乎不用证明了吧.最少4色.
以下是李宽证明法:
证明：

首先进行抽象处理:有颜色点表示地区，连线表示相邻及版图走向。

因为地图为平面，地区版图不可相叠覆盖。

所以连线不能交叉。

因为连线两端颜色不同。

所以两两相连的几个点颜色各不相同。

所以N个点两两相连共需N种颜色。

至此，四色问题转化为：在连线不允许交叉的前提下，最多有4个点可实现两两相连。也就是说，不可能有更多点两两相连，也就不可能出现更多色。

点数为1、2、3时均成立。由于线的形状，点的位置不影响相邻关系，故点数为3时两两相连可画成三角形。点数为4时，最终均可化为三角形内含有一点且该点与三顶点分别相连的形式。即有一点被三点封闭。

点数为5时，容易发现，无论第五点放在平面什么位置，都无法实现5个点在连线不交叉的前提下两两相连。（关键）

因为连线过程是递进的。即必然先满足三点两两相连，后满足四点两两相连，随后第五点。而已知第五点连线失败，点数更多也就不可能实现了。

环状地区，可抽象为环。环本身是封闭的。相对于环外点和环，环可视为点。在环内加点连线，最终可形成封闭区

点和环均定义为元素，欲用最少色涂最多元素，同时欲用更多色，必产生封闭区域。再用元素最少情况下，三点三线、一点一环两线、两点外一环三线为三种情况。在此基础上加点，最多四元素两两相连，最多为3+1=4色。（易操作）

无论多少元素建立连线，都不会出现多于四点两两相连情况。故最多四色。

由此，四色问题证毕。

G. 四色问题C语言怎么解决

思路：建立数据结构，录入数据内容，遍历着色，输出第一个可行的着色方案。

下面就四个方面详细分析一下

首先分析数据结构：

对于地图，一个区块包含一个唯一编号数据（这个编号可以是地名，也可以是数字）用来区分该区块和其他区块的不同

另外要着色，还要考虑该区块和其他区块连接的情况

最后就是区块本身的颜色

通过上面的分析，即可建立如下数据结构：

structarea{
intnID;//这里以数字替代名称，作为地块的唯一标识
intnColor;//用1,2,3,4表示不同的颜色，用0表示还没有着色
area*pNei;//邻接的区块
intnNei;//邻接区块的数量
};

然后需要录入数据，这个请依据具体的地图进行处理，撰写相应的录入函数，填入上面的数据结构

假设录好的数据如下：

structareacity[64];//假设已经录制好了数据，初始所有城市颜色都为0

数据录好后，我们可以如下方式进行遍历，尝试着色

遍历分为个模块：一个是遍历模块，一个是校验模块

校验模块依序检查所有的城市和其邻接城市是否存在同色的情况，是则返回false，否则返回true

遍历模块则逐个城市进行上色尝试

可以考虑递归

下面给一个递归的示例：

检测模块：

boolisOk(){
for(inti=0;i<64;i++)//假设有64个城市，其初始值和城市关系已经录制完毕
{
for(intj=0;j<city[i].nNei;j++){
if(nColor==city[i].pNei[j].nColor)
returnfalse;
}
}
returntrue;
}

遍历递归模块：

booladdcity(intnIndex){
if(nIndex>=64)returntrue;//所有城市都着色了，则返回成功
for(inti=1;i<=4;i++){
city[nIndex].nColor=i;
if(isOk()){//本城市的颜色找到了
if(addcity(nIndex+1)==true){//找下一个城市的颜色
returntrue;
}else{//无法为下一个城市着色
continue;//更改本城市颜色
}
}
}
returnfalse;//没有一个颜色可行，返回上一级，重新寻找
}

调用的时候可以采用下面的方式：

if(addcity(0)==false){
printf("无法找到答案，四色定理错误！
");
}else{
printf("找到了答案，城市和着色结果如下：
");
for(inti=0;i<64;i++){
printf("city%03dcolor%d
",city[i].nID,city[i].nColor);
}
}

H. c++，怎么解决地图着色问题

地图着色可以使用回溯的方法进行解决。

递归描述如下：

在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色。

这时候枚举可用的m个颜色，通过和与它相邻的节点的颜色，来判断这个颜色是否合法。

如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。

//用于判断当前节点上涂上这个颜色可不可行，与其邻接节点的颜色做判断，这里用邻接表来存储图的信息
boolisOk(intstep)
{
vector<int>::iteratoriter;
for(iter=input[step].begin();iter!=input[step].end();iter++)
{
if(Color[step]==Color[*iter])returnfalse;
}
returntrue;
}
//step表示0->n的节点，color_num是指给color_num的颜色的个数可用
//判断如果给color_num的颜色的个数是否可行，如果可行返回true,否则false
boolDFS(intstep,intcolor_num)
{
if(step>=n)returntrue;
else
{
inti;
for(i=1;i<=color_num;i++)
{
Color[step]=i;
if(isok(step))
{
if(DFS(step+1,color_num))
returntrue;
}
Color[step]=0;
}
}
returnfalse;
}

I. 急！利用5种不同的算法，为中国地图每个省着色，要求相邻的省份颜色不同，所用的颜色最少！！

这是根据数学史上着名的四色问题，每幅地图都可以用四种颜色着色，使得有共同代表地形的不同！颜色不代表什么，主要是为了区分方便，如果用同一种

地图着色算法c语言

与地图着色算法c语言相关的内容