数据结构地图着色问题

已知中国地图，请设计地图着色软件，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色最少。 【提示】 （1） 数据结构的设计：地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。 （2） 算法设计：设计着色算法，保证邻接点不是同一种颜色。 （3） 地图数据的输入采取从文件中读取。 （4） 结果输出方式可以采用图形方式或文本方式。

#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 vnumarcnum;     //图的顶点数和边数
}Graph;
//***********************************************************
int LocateVex（Graph Gchar u）
{ 
 int i;
 for（i=1;i<=G.vnum;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 ijk w;
 vextype v1v2;
 printf（“输入图的顶点数和边数:\n“）;
 scanf（“%d%d“&G.vnum&G.arcnum）;
 getchar（）;
 printf（“输入图的各顶点：\n“）;
 for（i=1;i<=G.vnum;i++）
 {
        scanf（“%c“&G.vexs[i]）; 
        getchar（）;
 } 
 for（i=0;i<=G.vnum;i++）
  for（j=0;j<=G.vnum;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（Gv1）;
   j=LocateVex（Gv2）;
   G.arcs[i][j]=w;
   G.arcs[j][i]=w;
  }
}
//****************************************************************
void PrintGraph（Graph G）   //输出图的信息
{
 int ij;
 printf（“图的各顶点：\n“）;
 for（i=1;i<=G.vnum;i++）
   printf（“%c “G.vexs[i]）;
 printf（“\n“）;
 printf（“图的邻接矩阵：\n“）;
 for（i=1;i<=G.vnum;i++）
 {
  for（j=1;j<=G.vnum;j++）
   printf（“%d  “G.arcs[i][j]）;
  printf（“\n“）;
 }
}
//******************************************************************
int colorsame（int sGraph G）//判断这个颜色能不能满足要求
{
    int iflag=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 sGraph G）//s为开始图色的顶点，本算法从1开始
{
    int i;
    if（s>G.vnum）//递归出口
    {
        output（G）;
        exit（1）;
    }
    else
    {
        for（i=1;i<=N;i++）//对每一种色彩逐个测试
        {
            color[s]=i;
            if（colorsame（sG）==0）
                trycolor（s+1G）;//进行下一块的着色
        }
    }
}
//*****************************************************************
int main（）
{ 
 Graph G;
 CreateGraph（G）;
 PrintGraph（G）;
 printf（“着色方案:\n“）;  
 trycolor（1G）;
  
 return 0;
}
  
 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      11710  2010-09-08 15:49  地图着色\测试图.png

     文件       5324  2009-05-03 13:16  地图着色\流程图.png

     文件       2812  2009-04-29 15:16  地图着色\地图着色.cpp

     文件      77824  2010-09-08 16:16  地图着色\作业2.doc

     文件       6833  2010-09-08 16:10  地图着色\示意图.png

     目录          0  2010-09-08 15:50  地图着色

----------- ---------  ---------- -----  ----

               104503                    6