数据结构课程设计
班级：
学号：
姓 名 ：
姓名：
班级：
学号：
题目：地图着色
一、需求分析：
1. 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；
2. 将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；
3. 演示程序以用户和计算机的对话方式进行；
4. 最后对结果做出简单分析。
二、概要设计：
1） 数据结构的设计
typedef struct //定义图
{
vextype vexs[MAXedg]; //存放边的矩阵
adjtype arcs[MAXedg][MAXedg]; //图的邻接矩阵
int vnum,arcnum; //图的顶点数和边数
}Graph;
2） 功能模块的划分及模块间调用关系
三、详细设计：
1） 主要功能模块的算法思想及其步骤
着色模块：
int colorsame(int s,Graph G)//判断这个颜色能不能满足要求
{
int i,flag=0;
for(i=1;i<=s-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<=G.vnum;i++)
printf("%d ",color[i]);
printf("\n");
}
void trycolor(int s,Graph G)//s 为开始图色的顶点
{
int i;
if(s>G.vnum)//递归出口
{
output(G);
exit(1);
}
else
{
for(i=1;i<=N;i++)//对每一种色彩逐个测试
{
color[s]=i;
if(colorsame(s,G)==0)
trycolor(s+1,G);//进行下一块的着色
}
}
}
2） 源程序清单
#include <stdio.h>
#include <stdlib.h>
#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;
