算法设计与分析课程设计
题目： 地图着色问题 文档：
物联网工程 学院业
学 号
学生姓名 班 级
二〇一三年十二月
一、问题描述：
地图着色问题
设计要求:已知中国地图, 对各省进行着色, 要求相邻省所使用的颜色不同, 并保证使用的颜色总数最少.
二、概要设计（流程图）
步骤：1．已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；
2．将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系；
3．将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求；
4．演示程序，以用户和计算机的对话方式进行；
5．最后对结果做出简单分析及总结。
流程图
三、源程序
#include
#include
#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
{
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
{
scanf("%c",&G.vexs[i]);
getchar();
}
for(i=0;i
for(j=0;j
G.arcs[i][j]=MAX;
printf("输入边的两个顶点和权值(均用1表示):\n");
for(k=0;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
printf("%c ",G.vexs[i]);
printf("\n");
printf("图的邻接矩阵：\n");
for(i=1;i
{
for(j=1;j
printf("%d ",G.arcs[i][j]);
printf("\n");
}
}
int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/
{
int i,flag=0;
for(i=1;i
if(G.arcs[i][s]==1&&color[i]==color[s])
{
flag=1;break;
}
return flag;
}
void output(Graph G)/*输出函数*/
int i;
for(i=1;i
printf("%d ",color[i]);
printf("\n");
}
void trycolor(int s,Graph G)/*s为开始图色的顶点，本算法从1开始*/
{
int i;
if(s>G.vnum)/*递归出口*/
{
output(G);
exit(1);
}
else
{
for(i=1;i
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);/*进行下一块的着色*/
}
}
}
int main()
{
Graph G;
CreateGraph(G);
PrintGraph(G);
printf("着色方案:\n");
trycolor(1,G);
return 0;
}
四、运行主要结果界面贴图
1、中国地图简略图
2、取地图一部分进行测试
有6个顶点，8条边。
各点相邻情况为：a-b ,a-e ,b-c ,b-d ,b-e ,c-d, d-e e-f
3、运行结果
五、总结
对中国地图着色即图着色问题，用m 种颜色来为无向图着色，其中顶点个数为n 。为此，用一个n 元组来描述图的一种着色。在这种着色中，所有相邻的顶点都不会具有相同的颜色，这种着色就是有效着色。根据这种思想编写中国地图着色算法，算法主要使用回溯法。根据算法运行，可以看出，无论有多少点，点与点之间怎样相邻，都只需要4种颜色就可以完成着色。
通过此次对中国地图着色问题的探究，我更好更深入了学习了着色问题中回溯法的运用，在课堂上学习的理论知识只有运用到实践里才能被更好的掌握。
算法设计与分析课程设计
题目： 地图着色问题 文档：
物联网工程 学院业
学 号
学生姓名 班 级
二〇一三年十二月
一、问题描述：
地图着色问题
设计要求:已知中国地图, 对各省进行着色, 要求相邻省所使用的颜色不同, 并保证使用的颜色总数最少.
二、概要设计（流程图）
步骤：1．已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；
2．将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系；
3．将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求；
4．演示程序，以用户和计算机的对话方式进行；
5．最后对结果做出简单分析及总结。
流程图
三、源程序
#include
#include
#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
{
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
{
scanf("%c",&G.vexs[i]);
getchar();
}
for(i=0;i
for(j=0;j
G.arcs[i][j]=MAX;
printf("输入边的两个顶点和权值(均用1表示):\n");
for(k=0;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
printf("%c ",G.vexs[i]);
printf("\n");
printf("图的邻接矩阵：\n");
for(i=1;i
{
for(j=1;j
printf("%d ",G.arcs[i][j]);
printf("\n");
}
}
int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/
{
int i,flag=0;
for(i=1;i
if(G.arcs[i][s]==1&&color[i]==color[s])
{
flag=1;break;
}
return flag;
}
void output(Graph G)/*输出函数*/
int i;
for(i=1;i
printf("%d ",color[i]);
printf("\n");
}
void trycolor(int s,Graph G)/*s为开始图色的顶点，本算法从1开始*/
{
int i;
if(s>G.vnum)/*递归出口*/
{
output(G);
exit(1);
}
else
{
for(i=1;i
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);/*进行下一块的着色*/
}
}
}
int main()
{
Graph G;
CreateGraph(G);
PrintGraph(G);
printf("着色方案:\n");
trycolor(1,G);
return 0;
}
四、运行主要结果界面贴图
1、中国地图简略图
2、取地图一部分进行测试
有6个顶点，8条边。
各点相邻情况为：a-b ,a-e ,b-c ,b-d ,b-e ,c-d, d-e e-f
3、运行结果
五、总结
对中国地图着色即图着色问题，用m 种颜色来为无向图着色，其中顶点个数为n 。为此，用一个n 元组来描述图的一种着色。在这种着色中，所有相邻的顶点都不会具有相同的颜色，这种着色就是有效着色。根据这种思想编写中国地图着色算法，算法主要使用回溯法。根据算法运行，可以看出，无论有多少点，点与点之间怎样相邻，都只需要4种颜色就可以完成着色。
通过此次对中国地图着色问题的探究，我更好更深入了学习了着色问题中回溯法的运用，在课堂上学习的理论知识只有运用到实践里才能被更好的掌握。