四色问题C语言怎么解决

四色问题C语言怎么解决

思路：建立数据结构，录入数据内容，遍历着色，输出第一个可行的着色方案。
　　下面就四个方面详细分析一下
　　首先分析数据结构：
　　对于地图，一个区块包含一个唯一编号数据（这个编号可以是地名，也可以是数字）用来区分该区块和其他区块的不同
　　另外要着色，还要考虑该区块和其他区块连接的情况
　　最后就是区块本身的颜色
　　通过上面的分析，即可建立如下数据结构：
struct area{
    int nID;//这里以数字替代名称，作为地块的唯一标识
    int nColor;//用1,2,3,4表示不同的颜色，用0表示还没有着色
    area* pNei;//邻接的区块
    int nNei;//邻接区块的数量
};　　然后需要录入数据，这个请依据具体的地图进行处理，撰写相应的录入函数，填入上面的数据结构

　　假设录好的数据如下：

struct area city[64];//假设已经录制好了数据，初始所有城市颜色都为0　　数据录好后，我们可以如下方式进行遍历，尝试着色

　　遍历分为个模块：一个是遍历模块，一个是校验模块
　　校验模块依序检查所有的城市和其邻接城市是否存在同色的情况，是则返回false，否则返回true
　　遍历模块则逐个城市进行上色尝试
　　可以考虑递归
　　下面给一个递归的示例：
　　检测模块：
bool isOk(){
for(int i=0;i<64;i++)//假设有64个城市，其初始值和城市关系已经录制完毕
{
    for(int j=0;j        if(nColor == city[i].pNei[j].nColor)
            return false;
    }
}
return true;
}　　遍历递归模块：

bool addcity(int nIndex){
    if(nIndex>=64) return true;//所有城市都着色了，则返回成功
    for(int i=1;i<=4;i++){
        city[nIndex].nColor=i;
        if(isOk()){//本城市的颜色找到了
            if(addcity(nIndex+1)==true){//找下一个城市的颜色
                return true;
            }else{//无法为下一个城市着色
                continue;//更改本城市颜色
            }
        }
    }
    return false;//没有一个颜色可行，返回上一级，重新寻找
}　　调用的时候可以采用下面的方式：

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

著名的四色定理是指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用 1～4 表示四种颜色。要着色的 N 个区域用 0～N一1编号,区域相邻关系用 adj[][] 矩阵表示,矩阵的 i 行 j 列的元素为 1 ,表示区域 i 与区域 j 相邻；矩阵的 i 行 j 列的元素为 0 ,表示区域 i 与区域 j 不相邻。数组 color[] 用来存储着色结果, color[i] 的值为区域 i 所着颜色。
另外,虚机团上产品团购,超级便宜

图论的面着色问题。
首先是要输入一个图。地图中的每一个区域在图中成为一个顶点(Vertex)，两个区域相邻在图中表示为两个顶点之间的一条边(Edge)。
这个要怎么输入呢？测试的时候可以先在代码里直接内置图的结构，要用户输入的话那就是UI的问题了。
输入完成以后，程序的内存里就有一张无向图了，图的表示方法，简单的可以用邻接矩阵来表示。
至于算法，一个比较简单的是深度优先搜索。
比如总共有10个顶点，那么至多有4^10种着色方案。
从(c1, c1, c1, c1, c1, c1, c1, c1, c1, c1)到(c4, c4, c4, c4, c4, c4, c4, c4, c4, c4)逐一判断即可。判断的过程中可以加入剪枝操作以提高效率。
比如(c1, c1, ...)这个方案在确定了2个顶点的颜色后已经矛盾了，那么就直接把后面的剪掉，从(c1, c2, ...)开始搜索

图论的面着色问题。
首先是要输入一个图。地图中的每一个区域在图中成为一个顶点(Vertex)，两个区域相邻在图中表示为两个顶点之间的一条边(Edge)。
这个要怎么输入呢？测试的时候可以先在代码里直接内置图的结构，要用户输入的话那就是UI的问题了。
输入完成以后，程序的内存里就有一张无向图了，图的表示方法，简单的可以用邻接矩阵来表示。
至于算法，一个比较简单的是深度优先搜索。
比如总共有10个顶点，那么至多有4^10种着色方案。
从(c1, c1, c1, c1, c1, c1, c1, c1, c1, c1)到(c4, c4, c4, c4, c4, c4, c4, c4, c4, c4)逐一判断即可。判断的过程中可以加入剪枝操作以提高效率。
比如(c1, c1, ...)这个方案在确定了2个顶点的颜色后已经矛盾了，那么就直接把后面的剪掉，从(c1, c2, ...)开始搜索