地图着色问题实验报告.docVIP

算法设计与分析课程设计 题目： 文档： 物联网工程 学院专业 学 号 学生姓名 班 级 二〇一三年月 地图着色问题设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.#include stdio.h #include stdlib.h #define MAXedg 100 #define MAX 0 #define N 4 /*着色的颜色数*/ int color[30]={0};/*来存储对应块的对应颜色*/ typedef char vextype; typedef int adjtype; typedef struct /*定义图*/ { vextype vexs[MAXedg]; /*存放边的矩阵*/ adjtype arcs[MAXedg][MAXedg]; /*图的邻接矩阵*/ int vnum,arcnum; /*图的顶点数和边数*/ }Graph; int LocateVex(Graph G,char u) { int i; for(i=1;i=G.vnum;i++) { if(u==G.vexs[i]) 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.vexs[i]); getchar(); } for(i=0;i=G.vnum;i++) for(j=0;j=G.vnum;j++) G.arcs[i][j]=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.arcs[i][j]=w; G.arcs[j][i]=w; } } void PrintGraph(Graph G) /*输出图的信息*/ { int i,j; printf(图的各顶点：\n); for(i=1;i=G.vnum;i++) printf(%c ,G.vexs[i]); printf(\n); printf(图的邻接矩阵：\n); for(i=1;i=G.vnum;i++) { for(j=1;j=G.vnum;j++) printf(%d ,G.arcs[i][j]); printf(\n); } } int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/ { int i,flag=0; for(i=1;i=s-1;i++)/*分别与前面已经着色的几块比较*/ if(G.arcs[i][s]==1color[i]==color[s]) { flag=1;break; } return flag; } void output(Graph G)/*输出函数*/ { int i; for(i=1;i=G.vnum;i++) printf(%d ,color[i]); printf(\n); } void trycolor(int s,Graph G)/*s为开始图色的顶点，本算法从1开始*/ { int i; if(sG.vnum)/*