地圖著色問題

1、一、 需求分析1、 問題描述現(xiàn)在有一張地圖，為了便于區(qū)別各個地圖上的板塊，地圖上相鄰的顏色塊應(yīng)該是不同的顏色?，F(xiàn)在的任務(wù)是給定一張地圖，要對其進行著色，相鄰的板塊之間的顏色不能相同，輸出最后的著色的方案。2、 基本分析功能一：為了程序的靈活性，可以讓程序自由建立圖功能二：為建好的圖進行著色。3、 輸入輸出輸入一張圖的信息，正確輸入邊數(shù)和頂點數(shù)，輸入邊的關(guān)系（兩個頂點之間的），顏色只要四種，分別用數(shù)字1到4表示。輸出時根據(jù)每個頂點不同的標號輸出著色的結(jié)果。二、 概要設(shè)計1、 設(shè)計思路給定四種顏色，從選定的第一個頂點開始著色，先是第一種顏色，如果這個顏色與這個頂點的其他鄰接頂點顏色不重復(fù)，則這個頂

2、點可以使用此顏色，程序開始對下一個頂點著色；如果著色重復(fù)，則使用下一種顏色重復(fù)上述過程。著色過程就是一個遞歸的過程，直到所有的頂點都有著色后結(jié)束著色過程開始對各省進行編號輸入圖的信息輸出圖的信息相鄰點顏色是否重復(fù)對點著色是否完成全部著色輸出結(jié)果結(jié)束2、 數(shù)據(jù)結(jié)構(gòu)設(shè)計：因為這個程序是對圖的操作，所以程序采用的邏輯結(jié)構(gòu)是圖狀，存儲結(jié)構(gòu)是鄰接矩陣，考慮用鄰接表是因為一般的地圖的某一個頂點并不會與很多的頂點鄰接，如果用鄰接矩陣就能符合實際的需求，雖然占用稍大的空間，但是增強了程序的實際使用性。抽象數(shù)據(jù)類型定義如下：數(shù)據(jù)對象是點和邊（vex&adj）數(shù)據(jù)關(guān)系是顏色分布以及邊的相鄰的兩個頂點基本操

3、作：CreatGrouph(&G);創(chuàng)建一張需要操作的無向圖GDestroy(Graph &G);初始條件：無向圖G存在操作結(jié)果：銷毀圖GLocateVex(&G,i)初始條件：無向圖G存在操作結(jié)果：若在圖G中存在頂點i，則返回該頂點在圖中的位置，否則返回其他信息Trycolor(current &G,store)初始條件：無向圖G存在，在圖中有第current個頂點操作結(jié)果：對圖開始遍歷，并且用他們的序號在store數(shù)組的相應(yīng)位置上存儲所染上的顏色。Print Graph(&G);初始條件：無向圖存在操作結(jié)果：打印圖G中 的每個頂點的顏色colorsa

4、me（test G）初始條件：無向圖G存在，test為圖中的一個頂點操作結(jié)果：如果圖中的test的鄰接點的顏色都不與test相同，則返回真，否則返回假。3、 軟件結(jié)構(gòu)設(shè)計本程序分為兩個模塊1、 主程序模塊Int main（）建立一張圖G建立存儲最終著色的結(jié)果的數(shù)組對地圖進行著色打印地圖著色情況銷毀圖退出2、 無向圖操作圖模塊-無向圖的中的節(jié)點賦值遍歷函數(shù)調(diào)用關(guān)系圖mainoutputPrintGraphCreateGraphtrycolor LocateVexcolorsame x colorsame詳細設(shè)計：typedef structvextype vexsMAXedg;adjtype a

5、rcsMAXedgMAXedg;int vnum,arcnum;Graph;用typedef struct建立結(jié)構(gòu)體Graph，包含點數(shù)組vexs與邊數(shù)組arcs還有兩者的數(shù)目int LocateVex(Graph G,char u) int i;for(i=1;i<G.vnum;i+)if(u=G.vexsi)return i;if(i=G.vnum)cout<<"Error u"<<endl;exit(1);return 0;儲存符合范式的點void CreateGraph(Graph &G)int i,j,k,w;vextype

6、v1,v2;cout<<"輸入圖的頂點數(shù)和變數(shù)"<<endl;cin>>G.vnum>>G.arcnum;cout<<"輸入圖的各頂點"<<endl;for(i=1;i<=G.vnum;i+)cin>>G.vexsi;for(i=0;i<=G.vnum;i+)for(j=0;j<=G.vnum;j+)G.arcsij=MAX;cout<<"輸入邊的兩個頂點和權(quán)值"<<endl;for(k=0;k<G.ar

7、cnum;k+)cin>>v1>>v2>>w;i = locateVex(G,v1);j= locateVex(G,v2);G.arcsji=w;完成對圖的初始化建立，輸入點，邊關(guān)系void PrintGraph(Graph G)int i,j;cout<<"圖的各個頂點"<<endl;for(i=1;i<=G.vnum;i+)cout<<G.vexsi;cout<<"圖的鄰接矩陣"<<endl;for(i=1;i<=G.vnum;j+)cout&

8、lt;<G.arcsij<<endl;打印圖的鄰接矩陣int colorsame(int s,Graph G)int i,flag=0;for(i=1;i<=s-1;i+)if(G.arcsis=1&&colori=colors)flag = 1;break;return flag;判斷是著色是否存在問題，對每條邊進行遍歷，相鄰的兩個點著色是否相等void output (Graph G)int i;for(i=1;i<=G.vnum;i+)cout<<colori<<endl;void trycolor(int s,Gra

9、ph G)int i;if(i>G.vnum)output(G);exit(1);elsefor(i=1;i<=N;i+)colors=i;if(colorsame(s,G)=0)trycolor(s+1,G); 輸出函數(shù)著色的方案嘗試給頂點著色，每次著色一個頂點，就遍歷相鄰關(guān)系的頂點一次，若不相同就使用這個顏色int main()Graph G;CreateGraph(G);PrintGraph(G);cout<<"著色方案"<<endl;trycolor(1,G);return 0;主函數(shù)main，調(diào)用其他函數(shù)完成地圖著色過程四、調(diào)試分析：本程序的主要功能是建立一個圖，然后對圖進行著色，數(shù)據(jù)類型為整型，用不同的數(shù)字表示不同的顏色。本程序的時間復(fù)雜度為n2。運行測試：五、體會與自我評價本次題目是我選擇的圖操作的一個問題，設(shè)計到圖的鄰接頂點的訪問和圖的遍歷。圖的存儲結(jié)構(gòu)我選擇的是矩陣的形式，在遍歷的時候是從第一條邊開始，查詢這邊