首页 > 代码库 > 地图四色着图的C语言实现

地图四色着图的C语言实现

四色问题又称四色猜想、四色定理,是世界三大数学猜想之一。四色定理是一个著名的数学定理,通俗的说法是:每个平面地图都可以只用四种颜色来染色,而且没有两个邻接的区域颜色相同。1976年借助电子计算机证明了四色问题,问题也终于成为定理,这是第一个借助计算机证明的定理。(这段文字来源于百度百科)

这篇文章主要介绍利用C语言实现地图四色着图。主要包括:设计的数据结构;算法实现等。


1 着图的数据结构

着图时无需表示具体的地图多边形,只需要表示多边形的Voronoi图即可,说的简单点可见下图:

对于左边的地图多边形,在算法中只需要表示成图形右边的即可。其中结点(v1, v2…)表示的是地图多边形,结点的连线表示两个多边形之间是比邻的关系。

因此在数据结构中只需要表示成图的形式即可。这里采用“邻接表”的数据结构,如下:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#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; i<=color_Num; i++) {
			G.vertics[step - 1].color = i;
			if(isColorOK(G, step)) {
				if(getColorPowset(G, color_Num, step + 1, a, b)) return true;
			}
			G.vertics[step - 1].color = 0;
		}
	}
	return false;
}

3 测试运行

测试过程的代码包括:建图的过程、输出着色结果的过程。这两个过程的代码如下:

int createUDGraph(UDGraph &G) {
	int a, b, i;
	ArcNList p;
	printf("请输入结点的个数和边的个数:");
	scanf("%d,%d", &(G.vexnum), &(G.arcnum));
	getchar(); //消除回车
	for(i=0; i<G.vexnum; i++) {//初始化各结点
		G.vertics[i].firstarc =NULL;
		G.vertics[i].color = 0;
	}
	printf("请输入这%d个点之间的拓扑关系:\n", G.vexnum);
	//接下来就是创建这G.arcnum*2个边
	for(i=1; i<=G.arcnum; i++) {
		scanf("%d,%d", &a, &b); //表明a点和b点之间向邻接,在a点和b点之间连上线
		getchar();//消除回车
		p = (ArcNList)malloc(sizeof(ArcNode)); if(!p) exit(-2);
		p->adjvex = b - 1;
		p->nextarc = G.vertics[a - 1].firstarc;
		G.vertics[a - 1].firstarc = p;
		//以上是在a点上加上一个结点,一下是在b点上加上一个结点
		p = (ArcNList)malloc(sizeof(ArcNode)); if(!p) exit(-2);
		p->adjvex = 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<G.vexnum; i++) printf("结点%d的着色方案为:%d\n", i+1, G.vertics[i].color);
}
int main() {
	int a, b;//a区域图b色
	UDGraph G;
	createUDGraph(G);
	printf("请输入一种着色方案(即哪一个区域着什么颜色):");
	scanf("%d,%d", &a, &b);//在a区域图上b色
	getchar();//消除回车
	if(getColorPowset(G, 4, 1, a, b)) {//如果最后的图色成功
		printf("图形图色成功,为:\n");
		outputGraph(G);
	} else printf("图形图色失败,方案不正确\n");//如果最后的图色成功
	return 1;
}

运行上述代码,测试如下:

其图形含义如下:



全文完。转载请注明出处。


地图四色着图的C语言实现