地图着色 数据结构.doc

数据结构课程设计 班级： 学号： 姓名：姓名：班级：学号：题目：地图着色一、 需求分析：1. 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2. 将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；3. 演示程序以用户和计算机的对话方式进行；4. 最后对结果做出简单分析。二、 概要设计：1） 数据结构的设计typedef struct /定义图 vextype vexsMAXedg; /存放边的矩阵 adjtype arcsMAXedgMAXedg; /图的邻接矩阵 int vnum,arcnum; /图的顶点数和边数Graph;2） 功能模块的划分及模块间调用关系 三、 详细设计：1） 主要功能模块的算法思想及其步骤着色模块：int colorsame(int s,Graph G)/判断这个颜色能不能满足要求 int i,flag=0; for(i=1;i=s-1;i+)/分别与前面已经着色的几块比较 if(G.arcsis=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);/进行下一块的着色 2） 源程序清单#include #include #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; for(i=1;i=G.vnum;i+) if(u=G.vexsi) return i; if(i=G.vnum) printf(Error u!n); exit(1); return 0;/*void CreateGraph(Graph &G) /输入图 int i,j,k, w; vextype v1,v2; printf(输入图的顶点数和边数:n); scanf(%d%d,&G.vnum,&G.arcnum); getchar(); printf(输入图的各顶点：n); for(i=1;i=G.vnum;i+) scanf(%c,&G.vexsi); getchar(); for(i=0;i=G.vnum;i+) for(j=0;j=G.vnum;j+) G.arcsij=MAX; printf(输入边的两个顶点和权值(均用1表示):n); for(k=0;kG.arcnum;k+) scanf(%c, &v1);getchar(); scanf(%c, &v2);getchar(); scanf(%d, &w); getchar(); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; /*void PrintGraph(Graph G) /输出图的信息 int i,j; printf(图的各顶点：n); for(i=1;i=G.vnum;i+) printf(%c ,G.vexsi); printf(n); printf(图的邻接矩阵：n); for(i=1;i=G.vnum;i+) for(j=1;j=G.vnum;j+) printf(%d ,G.arcsij); printf(n); /*int colorsame(int s,Graph G)/判断这个颜色能不能满足要求 int i,flag=0; for(i=1;i=s-1;i+)/分别与前面已经着色的几块比较 if(G.arcsis=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); PrintGraph(G); printf(着色方案:n); trycolor(1,G); return 0;四、 测试结果：由于地图上各省连