数据结构实验报告四-地图染色问题.doc

《数据结构实验报告四-地图染色问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验名称：实验五题目3地图染色问题学生姓名：xxx＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿班级：2013211128＿＿＿＿＿＿＿＿＿＿＿＿＿＿班内序号：xx＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿学号：2013210783＿＿＿＿＿＿＿＿＿＿＿＿＿＿日期：2014/12/19＿＿＿＿＿＿＿＿＿＿＿＿＿1.实验目的目的：Ø掌握图基本操作的实现方法Ø了解最小生成树的思想和相关概念Ø了解最短路径的思想和相关概念Ø学习使用图解决实际问题的能力内容：对下图所示的地图进行染色，要求使用尽可能少的颜色进行染色，完成该算法。测试数据：2.程序分析2.1存储结构二维数组struc

2、tColor{intNum;intLinks;};2.2程序流程对地图所对应的邻接矩阵按度排序顶点序号进行染色是否判断当前染色顶点与相邻顶点颜色是否相同重新寻找有效颜色进行染色染色下一个顶点直到所有顶点染色完毕，显示染色结果2.3关键算法分析算法1：voidArrange(intmap[][N],Colora[])[1]算法功能：对邻接矩阵的顶点按度进行排序[2]算法基本思想：计算每个顶点的度数，然后进行冒泡排序[3]算法空间、时间复杂度分析：O（n^2）[4]代码逻辑voidArrange(intmap[][N],Colora[]){for(inti=0;i

3、++){a[i].Num=i;a[i].Links=0;for(intj=0;j

4、[3]算法空间、时间复杂度分析：O（n）[4]代码逻辑boolflag(intmap[N][N],intver,intcol[])//判断该颜色是否可用{for(inti=0;i

5、行更改4.2心得体会通过这次的编程实验，我熟悉地掌握图基本操作的实现方法，了解了最小生成树的思想和相关概念，也明白了最短路径的思想和相关概念，并且学会了使用图解决实际问题，可谓受益匪浅。5.源程序#includeusingnamespacestd;constintN=7;structNODE{intID;intLinks;};voidSortNode(intb[][N],NODESN[]){for(inti=0;i

6、inks+=b[i][j];//计算每个顶点的度}for(inti=1;i

7、returnfalse;//i和k相邻，并且颜色相同，该颜色不合适returntrue;}voidmain(){intx[N]={0};//顶点颜色数组，用来保存最后的染色结果intb[N][N]={0,1,1,1,1,1,1,//所示的邻接矩阵1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0};NODENode[N];SortNode(b,Node);//按度数排序的顶点序号intk=0;while(k>=0){x[Node[k].