《地图着色问题实验报告文档.doc》由会员分享，可在线阅读，更多相关《地图着色问题实验报告文档.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 算法设计与分析课程设计题目： 地图着色问题 文档： 物联网工程 学 院 物联网工程 专 业 一、问题描述：地图着色问题设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.二、概要设计（流程图）步骤：1已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少； 2将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系； 3将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求； 4演示程序，以用户和计算机的对话方式进行； 5最后对结果做出简单分析及总结。 流程图 .- -三、源程序#include #i
2、nclude #define MAXedg 100 #define MAX 0 #define N 4 /*着色的颜色数*/ int color30=0;/*来存储对应块的对应颜色*/ typedef char vextype; typedef int adjtype; typedef struct /*定义图*/ vextype vexsMAXedg; /*存放边的矩阵*/ adjtype arcsMAXedgMAXedg; /*图的邻接矩阵*/ int vnum,arcnum; /*图的顶点数和边数*/ Graph; int LocateVex(Graph G,char u) int i;
3、 for(i=1;i=G.vnum;i+) if(u=G.vexsi) return i; if(i=G.vnum) exit(1); .- - return 0; void CreateGraph(Graph &G) /*输入图*/ int i,j,k, w; vextype v1,v2; 输入图的顶点数和边数 getchar(); 输入图的各顶点： for(i=1;i=G.vnum;i+) getchar(); for(i=0;i=G.vnum;i+) for(j=0;j=G.vnum;j+) G.arcsij=MAX; 输入边的两个顶点和权值(均用1表示 for(k=0;kG.arcnu
4、m;k+) i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; .- - void PrintGraph(Graph G) /*输出图的信息*/ int i,j; 图的各顶点： for(i=1;i=G.vnum;i+) 图的邻接矩阵： for(i=1;i=G.vnum;i+) for(j=1;j=G.vnum;j+) int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/ int i,flag=0; for(i=1;i=s-1;i+)/*分别与前面已经着色的几块比较*/ if(G.arc
5、sis=1&colori=colors) flag=1;break; return flag; void output(Graph G)/*输出函数*/ .- - int i; for(i=1;iG.vnum)/*递归出口*/ output(G); exit(1); else for(i=1;i=N;i+)/*对每一种色彩逐个测试*/ colors=i; if(colorsame(s,G)=0) trycolor(s+1,G);/*进行下一块的着色*/ int main() Graph G; CreateGraph(G); .- trycolor(1,G); return 0; 四、运行主要结
6、果界面贴图1、中国地图简略图2、取地图一部分进行测试有6个顶点，8条边。 各点相邻情况为：a-b ,a-e ,b-c ,b-d ,b-e ,c-d, d-e e-f 3、运行结果五、总结 对中国地图着色即图着色问题，用m种颜色来为无向图着色，其中顶点个数为n 。为此，用一个n元组来描述图的一种着色。在这种着色中，所有相邻的顶点都不会具有相同的颜色，这种着色就是有效着色。根据这种思想编写中国地图着色算法，算法主要使用回溯法。根据算法运行，可以看出，无论有多少点，点与点之间怎样相邻，都只需要4种颜色就可以完成着色。 通过此次对中国地图着色问题的探究，我更好更深入了学习了着色问题中回溯法的运用，在课堂上学习的理论知识只有运用到实践里才能被更好的掌握。 .-