地图四色着图的C语言实现 |
您所在的位置:网站首页 › 四色定理百科百度 › 地图四色着图的C语言实现 |
四色问题又称四色猜想、四色定理,是世界三大数学猜想之一。四色定理是一个著名的数学定理,通俗的说法是:每个平面地图都可以只用四种颜色来染色,而且没有两个邻接的区域颜色相同。1976年借助电子计算机证明了四色问题,问题也终于成为定理,这是第一个借助计算机证明的定理。(这段文字来源于百度百科) 这篇文章主要介绍利用C语言实现地图四色着图。主要包括:设计的数据结构;算法实现等。 1 着图的数据结构 着图时无需表示具体的地图多边形,只需要表示多边形的Voronoi图即可,说的简单点可见下图: 对于左边的地图多边形,在算法中只需要表示成图形右边的即可。其中结点(v1, v2…)表示的是地图多边形,结点的连线表示两个多边形之间是比邻的关系。 因此在数据结构中只需要表示成图的形式即可。这里采用“邻接表”的数据结构,如下: #include #include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; //该边指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 } ArcNode, *ArcNList; typedef struct { float x; float y; } Vertex; //点 typedef struct VNode { Vertex data; //顶点信息 ArcNList firstarc; //指向第一条依附该顶点的边的指针 int color; //该点的颜色 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertics; int vexnum, arcnum; //该图的当前顶点数和边数 } UDGraph; 2 着图的算法着色的算法采用回溯法。基本思路为:首先对一个多边形进行着色,着色后判断是否满足要求,如果满足要求则继续对其他多边形进行着色;如果不满足要求则撤销当前着色并回溯,采用其他着色方案。递归如此,直到地图全部着色完成。 地图四色染图的C语言代码实现如下。其首先给定地图最多使用的颜色数量为4,判断能否只利用4种颜色对地图进行着色,如果能则返回true,反之则返回false。 bool isColorOK(UDGraph G, int node) { //判断对第node个结点着色的方案行不行 VNode V = G.vertics[node - 1]; ArcNList T = V.firstarc; while(T) { if(V.color == G.vertics[T->adjvex].color) return false; T = T->nextarc; } return true; } bool getColorPowset(UDGraph &G, int color_Num, int step, int a, int b) { //**回溯法对图着色 if(step > G.vexnum) { if(G.vertics[a-1].color == b) { //在a区域图上了b色 return true; } } else { int i; for(i=1; iadjvex = a - 1; p->nextarc = G.vertics[b - 1].firstarc; G.vertics[b - 1].firstarc = p; } return 1; } void outputGraph(UDGraph G) { int i; for(i=0; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |