关于江苏省地图的着色问题

问题介绍

地图着色问题是一个抽象的图形学问题，用程序实现对各个区域进行着色，并且相邻区域所用的颜色不同，同时保证颜色的总数最少，那么就是如何将这些抽象的问题进行数据化。如何将程序所需要的功能模拟着色在计算机中编程实现。

问题解决

先将每个城市与城市分界线进行数字化，将每个城市的地图颜色设为初始值0即为白色，在循环中判断目前城市的颜色和与当前城市有分界线的城市是否存在颜色相同。如果存在就将数字加一（改变颜色）。

流程图

初始化模块

typedef structArcNode
{
int x;   // 表示与当前顶点所表示城市相邻的省份的位置信息
 	struct ArcNode *next;    // 指向下一个弧结点
}ArcNode;    // 表示城市之间相邻关系的弧结点
typedef struct
{
  char *name;  // 顶点所表示的城市的名称
   int color;    // 城市的颜色，用数字表示不同的颜色
   ArcNode *firstnext;  // 指向第一个弧
}City[13];

着色模块

for(i=1;i<=13;i++)
	{
		city[i].color=0;
	}
	for(i=1;i<=13;i++)
	{
		j=1;
		p=city[i].firstnext;
		while(p!=NULL)
		{
			while(p!=NULL&&j!=city[p->x].color)
			{
				p=p->next;
			}
			if(p!=NULL) 
				j++;
		}
		city[i].color=j;
	}

输出模块

for(i=1;i<=13;i++)
	{
		printf("%s:",city[i].name);
		printf("%d\n",city[i].color);
	}

详细代码

#include <stdio.h>
#include <stdlib.h>
typedef struct ArcNode{
	int x;         // 表示与当前顶点所表示城市相邻的省份的位置信息
	struct ArcNode *next;
}ArcNode;       // 表示城市之间相邻关系的弧结点
typedef struct{
	char *name;   // 顶点所表示的城市的名称
	int color;
	ArcNode *firstnext;  // 指向第一个弧
}City[13];
int main()
{
	City city;
	int i,j;
	ArcNode
*p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*hu10,*hu11,*hu12,*hu13,*hu14,*hu15,*hu16,*hu17,*hu18;
	ArcNode *hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu31,*hu32,*hu33,*hu34,*hu35;
	ArcNode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;
	ArcNode *hu53,*hu54,*hu55,*hu56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62;//声明表示城市顶点的信息
	hu1=(ArcNode *)malloc(sizeof(ArcNode));
	hu2=(ArcNode *)malloc(sizeof(ArcNode));
	hu3=(ArcNode *)malloc(sizeof(ArcNode));
	hu4=(ArcNode *)malloc(sizeof(ArcNode));
	hu5=(ArcNode *)malloc(sizeof(ArcNode));
	hu6=(ArcNode *)malloc(sizeof(ArcNode));
	hu7=(ArcNode *)malloc(sizeof(ArcNode));
	hu8=(ArcNode *)malloc(sizeof(ArcNode));
	hu9=(ArcNode *)malloc(sizeof(ArcNode));
	hu10=(ArcNode *)malloc(sizeof(ArcNode));
	hu11=(ArcNode *)malloc(sizeof(ArcNode));
	hu12=(ArcNode *)malloc(sizeof(ArcNode));
	hu13=(ArcNode *)malloc(sizeof(ArcNode));
	hu14=(ArcNode *)malloc(sizeof(ArcNode));
	hu15=(ArcNode *)malloc(sizeof(ArcNode));
	hu16=(ArcNode *)malloc(sizeof(ArcNode));
	hu17=(ArcNode *)malloc(sizeof(ArcNode));
	hu18=(ArcNode *)malloc(sizeof(ArcNode));
	hu19=(ArcNode *)malloc(sizeof(ArcNode));
	hu20=(ArcNode *)malloc(sizeof(ArcNode));
	hu21=(ArcNode *)malloc(sizeof(ArcNode));
	hu22=(ArcNode *)malloc(sizeof(ArcNode));
	hu23=(ArcNode *)malloc(sizeof(ArcNode));
	hu24=(ArcNode *)malloc(sizeof(ArcNode));
	hu25=(ArcNode *)malloc(sizeof(ArcNode));
	hu26=(ArcNode *)malloc(sizeof(ArcNode));
	hu27=(ArcNode *)malloc(sizeof(ArcNode));
	hu28=(ArcNode *)malloc(sizeof(ArcNode));
	hu29=(ArcNode *)malloc(sizeof(ArcNode));
	hu30=(ArcNode *)malloc(sizeof(ArcNode));
	hu31=(ArcNode *)malloc(sizeof(ArcNode));
	hu32=(ArcNode *)malloc(sizeof(ArcNode));
	hu33=(ArcNode *)malloc(sizeof(ArcNode));
	hu34=(ArcNode *)malloc(sizeof(ArcNode));
	hu35=(ArcNode *)malloc(sizeof(ArcNode));
	hu36=(ArcNode *)malloc(sizeof(ArcNode));
	hu37=(ArcNode *)malloc(sizeof(ArcNode));
	hu38=(ArcNode *)malloc(sizeof(ArcNode));
	hu39=(ArcNode *)malloc(sizeof(ArcNode));
	hu40=(ArcNode *)malloc(sizeof(ArcNode));
	hu41=(ArcNode *)malloc(sizeof(ArcNode));
	hu42=(ArcNode *)malloc(sizeof(ArcNode));
	hu43=(ArcNode *)malloc(sizeof(ArcNode));
	hu44=(ArcNode *)malloc(sizeof(ArcNode));
	hu45=(ArcNode *)malloc(sizeof(ArcNode));
	hu46=(ArcNode *)malloc(sizeof(ArcNode));
	hu47=(ArcNode *)malloc(sizeof(ArcNode));
	hu48=(ArcNode *)malloc(sizeof(ArcNode));
	hu49=(ArcNode *)malloc(sizeof(ArcNode));
	hu50=(ArcNode *)malloc(sizeof(ArcNode));
	hu51=(ArcNode *)malloc(sizeof(ArcNode));
	hu52=(ArcNode *)malloc(sizeof(ArcNode));
	hu53=(ArcNode *)malloc(sizeof(ArcNode));
	hu54=(ArcNode *)malloc(sizeof(ArcNode));
	hu55=(ArcNode *)malloc(sizeof(ArcNode));
	hu56=(ArcNode *)malloc(sizeof(ArcNode));
	hu57=(ArcNode *)malloc(sizeof(ArcNode));
	hu58=(ArcNode *)malloc(sizeof(ArcNode));
	hu59=(ArcNode *)malloc(sizeof(ArcNode));
	hu60=(ArcNode *)malloc(sizeof(ArcNode));
	hu61=(ArcNode *)malloc(sizeof(ArcNode));
	hu62=(ArcNode *)malloc(sizeof(ArcNode));
	city[1].name="苏州市";
	hu1->x=2;
	hu2->x=8;
	hu3->x=7; 
	city[1].firstnext=hu1;//声名表示城市之间相邻的弧
	hu1->next=hu2;
	hu2->next=hu3;
	hu3->next=NULL;
	city[2].name="无锡市";
	hu4->x=3;
	hu5->x=7;
	hu6->x=1;
	city[2].firstnext=hu4;
	hu4->next=hu5;
	hu5->next=hu6;
	hu6->next=NULL;
	city[3].name="常州市";
	hu7->x=4;
	hu8->x=5;
	hu9->x=2;
	hu10->x=7;
	city[3].firstnext=hu7;
	hu7->next=hu8;
	hu8->next=hu9;
	hu9->next=hu10;
	hu10->next=NULL;
	city[4].name="镇江市";
	hu12->x=6;
	hu13->x=7;
	hu14->x=3;
	hu11->x=5; 
	city[4].firstnext=hu12;
	hu12->next=hu13;
	hu13->next=hu14;
	hu14->next=hu11;
	hu11->next=NULL;
	city[5].name="南京市";
	hu15->x=6;
	hu16->x=10;
	hu18->x=3; 
	hu17->x=4;
	city[5].firstnext=hu15;
	hu15->next=hu16;
	hu16->next=hu18;
	hu18->next=hu17;
	hu17->next=NULL;
	city[6].name="扬州市";
	hu19->x=7;
	hu20->x=9;
	hu21->x=10;
	hu22->x=5;
	hu23->x=4; 
	city[6].firstnext=hu19;
	hu19->next=hu20;
	hu20->next=hu21;
	hu21->next=hu22;
	hu22->next=hu23;
	hu23->next=NULL;
	city[7].name="泰州市";
	hu24->x=8; 
	hu26->x=1;
	hu27->x=2;
	hu28->x=3;
	hu29->x=4;
	hu30->x=6; 
	hu60->x=9;
	city[7].firstnext=hu24;
	hu24->next=hu26;
	hu26->next=hu27;
	hu27->next=hu28;
	hu28->next=hu29;
	hu29->next=hu30;
	hu30->next=hu60;
	hu60->next=NULL;
	city[8].name="南通市";
	hu32->x=1;
	hu33->x=7;
	hu57->x=9;
	city[8].firstnext=hu32;
	hu32->next=hu33;
		hu33->next=hu57;
	hu57->next=NULL;
	city[9].name="盐城市";
	hu35->x=11;
	hu38->x=6;
	hu55->x=10;
	hu58->x=8;
	hu61->x=7;
	city[9].firstnext=hu35;
	hu35->next=hu38;
	hu38->next=hu55;
	hu55->next=hu58;
	hu58->next=hu61;
	hu61->next=NULL;
	city[10].name="淮安市";
    hu39->x=11;
	hu40->x=12;

	hu42->x=6;
	hu43->x=5;
	hu56->x=9;
	city[10].firstnext=hu39;
hu39->next=hu40;
	hu40->next=hu42;
	hu42->next=hu43;
	hu43->next=hu56;
	hu56->next=NULL;
	city[11].name="连云港市";
	hu44->x=12;
	hu45->x=13;
	hu46->x=10;
	hu47->x=9;
	city[11].firstnext=hu44;
	hu44->next=hu45;
	hu45->next=hu46;
	hu46->next=hu47;
	hu47->next=NULL;
	city[12].name="宿迁市";
	hu48->x=13;
	hu49->x=11;
	hu50->x=10;
	city[12].firstnext=hu48;
		hu48->next=hu49;
	hu49->next=hu50;
	hu50->next=NULL;
	city[13].name="徐州市";
	hu51->x=11;
	hu52->x=12;
	city[13].firstnext=hu51;
	hu51->next=hu52;
	hu52->next=NULL;
	

	for(i=1;i<=13;i++)
	{
		city[i].color=0;
	}
	for(i=1;i<=13;i++)
	{
		j=1;
		p=city[i].firstnext;
		while(p!=NULL)
		{
			while(p!=NULL&&j!=city[p->x].color)
			{
				p=p->next;
			}
			if(p!=NULL)
				j++;
		}
		city[i].color=j;
	}//分别为各城市着色
	for(i=1;i<=13;i++)
	{
		printf("%s:",city[i].name);
		printf("%d\n",city[i].color);
	}//输出各城市颜色信息
        printf("/n 0表示白色,1表示蓝色,2表示红色,3表示绿色,4表示黄色");
	return 0;
	}