#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