数据结构——地图填色问题

《数据结构——地图填色问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》实验报告院系光电与信息工程学院专业电子信息工程姓名学号电话2011级2班2013年5月22日一、实验题目数据结构——期末综合实验——地图填色问题二、问题描述1976年。美国科学家APPEL和HAKEN利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。要求输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案个数。三、数据描述首先考虑如何存储行政区域图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。G[I,J]=1表示I，J两个行政区域相邻

2、，为0表示不相邻可采用二维数组来表示邻接矩阵G；另外设一数组COLOR[I]记录各行政区域所填颜色，分别取值为｛1（红色），2（黄色），3（蓝色），4（绿色）｝；数据描述如下：INTG[N][N];INTCOLOR[N+1];四、概要设计（1）全局变量定义#defineMAX_VERTEX_NUM26//最大行政区域个数//-------------------------------邻接矩阵数据类型的定义--------------------------------typedefstruct{charvexs[MAX_VERTEX_NUM];//行政区域-顶点向量

3、intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum;//地图当前行政区域个数}Graph;intColor[MAX_VERTEX_NUM+1];//地图行政区域填充的颜色存储数组longintCount=0;//统计总共的填色方案个数（2）本程序主要包含6个函数：主函数main()创建地图及行政区域的邻接矩阵Create_Graph()12显示行政区域的邻接矩阵关系Printf_Graph()对地图行政区域进行第一次着色Load_Color()对地图行政区域进行各种方案着色的显Print_Color()判断这

4、个颜色对第n行政区域能不能满足要求Same_Color（）Create_Graph各函数间调用关系如下：Printf_GraphMain（）Load_ColorSame_ColorPrint_Color（1）主函数的伪码main(){定义一个邻接矩阵G；创建地图及行政区域的邻接矩阵；显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；}一、详细设计//-------------------------------邻接矩阵数据类型的定义--------------------------------#defineMAX_VERTEX_NUM26//最

5、大行政区域个数typedefstruct{charvexs[MAX_VERTEX_NUM];//行政区域-顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum;//地图当前行政区域个数}Graph;/*****************************************************************************************函数：Create_Graph*功能：建立地图的邻接矩阵*说明：输入参数Graph*G本函数很好的完成了地图的创建以及行政区域之间

6、的存储。在输入错误的时候，会有相应的指示，使得程序更加健壮。****************************************************************************************/voidCreate_Graph(Graph*G)//建立地图行政区域的邻接矩阵{输入地图的行政区域的个数G->vexnum；输入行政区域，构造行政区域-顶点向量；初始化邻接矩阵都为0；构造行政区域邻接矩阵；12｛输入与V1相邻的行政区域，存放于S数组中；相邻的行政区域G->acrs[i][j]=1；｝}/**************

7、***************************************************************************函数：Printf_Graph*功能：显示地图行政区域的邻接矩阵*说明：输入参数GraphG。本函数很好的完成了地图行政区域的邻接矩阵的显示****************************************************************************************/voidPrintf_Graph(GraphG){构造图形；横向显示行政区域；纵向显示行