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

数 据 结 构实验报告实验名称： 实验五 题目3 地图染色问题 学生姓名： xxx 班 级： 2013211128班内序号： xx学 号： 2013210783日 期： 2014/12/19 1. 实验目的目的： 掌握图基本操作的实现方法 了解最小生成树的思想和相关概念 了解最短路径的思想和相关概念 学习使用图解决实际问题的能力内容：对下图所示的地图进行染色，要求使用尽可能少的颜色进行染色，完成该算法。测试数据：2. 程序分析2.1 存储结构二维数组struct Colorint Num;int Links; 2.2 程序流程 对地图所对应的邻接矩阵按度排序顶点序号 进行染色是否判断当前染色顶点与相邻顶点颜色是否相同重新寻找有效颜色进行染色染色下一个顶点直到所有顶点染色完毕，显示染色结果2.3 关键算法分析 算法1：void Arrange(int mapN,Color a) 1 算法功能：对邻接矩阵的顶点按度进行排序 2 算法基本思想：计算每个顶点的度数，然后进行冒泡排序 3 算法空间、时间复杂度分析：O（n2） 4 代码逻辑void Arrange(int mapN,Color a)for (int i=0;iN;i+)ai.Num=i;ai.Links=0;for (int j=0;jN;j+)ai.Links=ai.Links+mapij;for (int i=1;iN;i+)for (int j=0; jN-i;j+)if (aj.Linksaj+1.Links)Color tmp=aj;aj=aj+1;aj+1=tmp; 算法2：bool flag(int mapNN, int ver, int col) 1 算法功能：判断相邻顶点的颜色是否重复 2 算法基本思想：比较相邻顶点的颜色是否相同，相同的话返回值为false 3 算法空间、时间复杂度分析：O（n） 4 代码逻辑bool flag(int mapNN, int ver, int col) /判断该颜色是否可用 for(int i=0; iN; i+) if(mapveri=0) continue; /顶点i和顶点ver不相邻，继续 else if(colver=coli) return false; /i和ver相邻，并且颜色相同，该颜色不合适 return true; 3程序运行结果分析4总结4.1实验的难点和关键点 难点及关键点：对相邻顶点的颜色进行判断比较，如果相同则需要替换用一个bool值来判断是否对颜色进行更改4.2心得体会 通过这次的编程实验，我熟悉地掌握图基本操作的实现方法，了解了最小生成树的思想和相关概念，也明白了最短路径的思想和相关概念，并且学会了使用图解决实际问题，可谓受益匪浅。5.源程序#include using namespace std; const int N = 7;struct NODE int ID; int Links; ; void SortNode(int bN,NODE SN) for (int i=0;iN;i+) SNi.ID = i; SNi.Links = 0; /初始化顶点信息 for (int j=0;jN;j+) SNi.Links += bij; /计算每个顶点的度 for (int i=1;iN;i+) /冒泡排序 for (int j=0; jN-i;j+) if (SNj.LinksSNj+1.Links) NODE tmp = SNj; SNj = SNj+1; SNj+1 = tmp; bool IsValid(int bNN, int k, int x) /判断该颜色是否可用，b是邻接矩阵，k是当前染色的顶点序号，x是顶点颜色数组 for(int i=0; i=0) xNodek.ID = xNodek.ID + 1; while(!IsValid(b, Nodek.ID, x) /着色无效继续再当前层搜索有效的颜色 xNodek.ID = xNodek.ID + 1; if(k=N-1) break