地图着色问题

1、一、 需求分析1、 问题描述现在有一张地图，为了便于区别各个地图上的板块，地图上相邻的颜色块应该是不同的颜色。现在的任务是给定一张地图，要对其进行着色，相邻的板块之间的颜色不能相同，输出最后的着色的方案。2、 基本分析功能一：为了程序的灵活性，可以让程序自由建立图功能二：为建好的图进行着色。3、 输入输出输入一张图的信息，正确输入边数和顶点数，输入边的关系（两个顶点之间的），颜色只要四种，分别用数字1到4表示。输出时根据每个顶点不同的标号输出着色的结果。二、 概要设计1、 设计思路给定四种颜色，从选定的第一个顶点开始着色，先是第一种颜色，如果这个颜色与这个顶点的其他邻接顶点颜色不重复，则这个顶

2、点可以使用此颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上述过程。着色过程就是一个递归的过程，直到所有的顶点都有着色后结束着色过程开始对各省进行编号输入图的信息输出图的信息相邻点颜色是否重复对点着色是否完成全部着色输出结果结束2、 数据结构设计：因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构是邻接矩阵，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点邻接，如果用邻接矩阵就能符合实际的需求，虽然占用稍大的空间，但是增强了程序的实际使用性。抽象数据类型定义如下：数据对象是点和边（vex&adj）数据关系是颜色分布以及边的相邻的两个顶点基本操

3、作：CreatGrouph(&G);创建一张需要操作的无向图GDestroy(Graph &G);初始条件：无向图G存在操作结果：销毁图GLocateVex(&G,i)初始条件：无向图G存在操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息Trycolor(current &G,store)初始条件：无向图G存在，在图中有第current个顶点操作结果：对图开始遍历，并且用他们的序号在store数组的相应位置上存储所染上的颜色。Print Graph(&G);初始条件：无向图存在操作结果：打印图G中 的每个顶点的颜色colorsa

4、me（test G）初始条件：无向图G存在，test为图中的一个顶点操作结果：如果图中的test的邻接点的颜色都不与test相同，则返回真，否则返回假。3、 软件结构设计本程序分为两个模块1、 主程序模块Int main（）建立一张图G建立存储最终着色的结果的数组对地图进行着色打印地图着色情况销毁图退出2、 无向图操作图模块-无向图的中的节点赋值遍历函数调用关系图mainoutputPrintGraphCreateGraphtrycolor LocateVexcolorsame x colorsame详细设计：typedef structvextype vexsMAXedg;adjtype a

5、rcsMAXedgMAXedg;int vnum,arcnum;Graph;用typedef struct建立结构体Graph，包含点数组vexs与边数组arcs还有两者的数目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)cout<<"Error u"<<endl;exit(1);return 0;储存符合范式的点void CreateGraph(Graph &G)int i,j,k,w;vextype

6、v1,v2;cout<<"输入图的顶点数和变数"<<endl;cin>>G.vnum>>G.arcnum;cout<<"输入图的各顶点"<<endl;for(i=1;i<=G.vnum;i+)cin>>G.vexsi;for(i=0;i<=G.vnum;i+)for(j=0;j<=G.vnum;j+)G.arcsij=MAX;cout<<"输入边的两个顶点和权值"<<endl;for(k=0;k<G.ar

7、cnum;k+)cin>>v1>>v2>>w;i = locateVex(G,v1);j= locateVex(G,v2);G.arcsji=w;完成对图的初始化建立，输入点，边关系void PrintGraph(Graph G)int i,j;cout<<"图的各个顶点"<<endl;for(i=1;i<=G.vnum;i+)cout<<G.vexsi;cout<<"图的邻接矩阵"<<endl;for(i=1;i<=G.vnum;j+)cout&

8、lt;<G.arcsij<<endl;打印图的邻接矩阵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;i<=G.vnum;i+)cout<<colori<<endl;void trycolor(int s,Gra

9、ph G)int i;if(i>G.vnum)output(G);exit(1);elsefor(i=1;i<=N;i+)colors=i;if(colorsame(s,G)=0)trycolor(s+1,G); 输出函数着色的方案尝试给顶点着色，每次着色一个顶点，就遍历相邻关系的顶点一次，若不相同就使用这个颜色int main()Graph G;CreateGraph(G);PrintGraph(G);cout<<"着色方案"<<endl;trycolor(1,G);return 0;主函数main，调用其他函数完成地图着色过程四、调试分析：本程序的主要功能是建立一个图，然后对图进行着色，数据类型为整型，用不同的数字表示不同的颜色。本程序的时间复杂度为n2。运行测试：五、体会与自我评价本次题目是我选择的图操作的一个问题，设计到图的邻接顶点的访问和图的遍历。图的存储结构我选择的是矩阵的形式，在遍历的时候是从第一条边开始，查询这边