数据结构——地图填色问题

《数据结构》实验报告

院系 光电与信息工程学院 专业 电子信息工程

姓名 学号 电话 2011级 2班 2013年5月22日

一、 实验题目

数据结构——期末综合实验——地图填色问题

二、 问题描述

1976年。美国科学家APPEL和HAKEN利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。要求输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案个数。

三、 数据描述

首先考虑如何存储行政区域图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。

G[ I , J ]=1 表示I ， J 两个行政区域相邻，为0表示不相邻 可采用二维数组来表示邻接矩阵G；另外设一数组COLOR[I]记录各行政区域所填颜色，分别取值为｛1（红色），2（黄色），3（蓝色），4（绿色）｝；数据描述如下：

INT G[N][N];

INT COLOR[N+1];

四、 概要设计

（1） 全局变量定义

#define MAX_VERTEX_NUM 26

//------------------------------- 邻接矩阵数据类型的定义-------------------------------- typedef struct {

char vexs[MAX_VERTEX_NUM]; int vexnum;

// 行政区域-顶点向量 // 地图当前行政区域个数

// 地图行政区域填充的颜色存储数组 // 统计总共的填色方案个数

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];// 邻接矩阵 }Graph ;

int Color[MAX_VERTEX_NUM+1]; long int Count=0;

（2） 本程序主要包含6个函数：

主函数

main()

// 最大行政区域个数

（3） 主函数的伪码

main() {

定义一个邻接矩阵 G；

创建地图及行政区域的邻接矩阵； 显示行政区域的邻接矩阵关系； 对地图进行填充颜色； 改变颜色，显示多种方案； }

Print_Color

Main（）

Load_Color

Same_Color

Printf_Graph

显示行政区域的邻接矩阵关系

Printf_Graph () Load_Color () Print_Color () Same_Color（）

对地图行政区域进行第一次着色

对地图行政区域进行各种方案着色的显 各函数间调用关系如下：

判断这个颜色对第n行政区域能不能满足要求

Create_Graph

五、 详细设计

//------------------------------- 邻接矩阵数据类型的定义-------------------------------- #define MAX_VERTEX_NUM 26 // 最大行政区域个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 行政区域-顶点向量 int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum; // 地图当前行政区域个数 }Graph ;

/**************************************************************************************** *函数：Create_Graph

*功能：建立地图的邻接矩阵 *说明：输入参数 Graph *G 本函数很好的完成了地图的创建以及行政区域之间的存储。 在输入错误的时候，会有相应的指示，使得程序更加健壮。

****************************************************************************************/ void Create_Graph( Graph *G ) // 建立地图行政区域的邻接矩阵 { 输入地图的行政区域的个数G->vexnum ； 输入行政区域，构造行政区域-顶点向量 ；

初始化邻接矩阵都为0； 构造行政区域邻接矩阵；

｛

输入与V1 相邻的行政区域，存放于 S 数组中； 相邻的行政区域G->acrs[i][j]=1； ｝

}

/**************************************************************************************** *函数：Printf_Graph

*功能：显示地图行政区域的邻接矩阵 *说明：输入参数 Graph G 。 本函数很好的完成了地图行政区域的邻接矩阵的显示

****************************************************************************************/ void Printf_Graph( Graph G ) { 构造图形；

横向显示 行政区域； 纵向显示 行政区域； 显示邻接矩阵； }

/**************************************************************************************** *函数：Same_Color

*功能：判断这个颜色对第n行政区域能不能满足要求 *说明：输入参数 Graph G，int n， 输出 0 则表示满足，输出 1 则表示不满足

****************************************************************************************/ int Same_Color(Graph G,int n) { Color[n]分别与前面已经着色的几块比较；

相邻并且颜色一样，则不满足； 颜色满足 返回0 颜色不满足 返回 1 }

/**************************************************************************************** *函数：Load_Color

*功能：对地图行政区域进行第一次着色 ，始之满足要求 *说明：输入参数 Graph G，int n

****************************************************************************************/ void Load_Color( Graph G , int n ) { 取一种颜色

If(颜色满足，没有与前面冲突)

下一块行政区域着色Load_Color(G,n+1);

Else 尝试另一种颜色 }

/**************************************************************************************** *函数：Print_Color

*功能：对地图行政区域进行各种方案的显示。 *说明：输入参数 Graph G，int m 注意：调用本函数的前提是Color[]数组中有一个正确的填充颜色的方案。

****************************************************************************************/ void Print_Color( Graph G , int m) { for(i=1;i<=4;i++)

更换颜色，新的颜色 …… 此处隐藏：6859字，全部文档内容请下载后查看。喜欢就下载吧 ……