地圖著色問(wèn)題

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

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

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

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

5、rcsMAXedgMAXedg;int vnum,arcnum;Graph;用typedef struct建立結(jié)構(gòu)體Graph，包含點(diǎn)數(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;儲(chǔ)存符合范式的點(diǎn)void CreateGraph(Graph &G)int i,j,k,w;vextype

6、v1,v2;cout<<"輸入圖的頂點(diǎn)數(shù)和變數(shù)"<<endl;cin>>G.vnum>>G.arcnum;cout<<"輸入圖的各頂點(diǎn)"<<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<<"輸入邊的兩個(gè)頂點(diǎn)和權(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;完成對(duì)圖的初始化建立，輸入點(diǎn)，邊關(guān)系void PrintGraph(Graph G)int i,j;cout<<"圖的各個(gè)頂點(diǎn)"<<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;判斷是著色是否存在問(wèn)題，對(duì)每條邊進(jìn)行遍歷，相鄰的兩個(gè)點(diǎn)著色是否相等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ù)著色的方案嘗試給頂點(diǎn)著色，每次著色一個(gè)頂點(diǎn)，就遍歷相鄰關(guān)系的頂點(diǎn)一次，若不相同就使用這個(gè)顏色int main()Graph G;CreateGraph(G);PrintGraph(G);cout<<"著色方案"<<endl;trycolor(1,G);return 0;主函數(shù)main，調(diào)用其他函數(shù)完成地圖著色過(guò)程四、調(diào)試分析：本程序的主要功能是建立一個(gè)圖，然后對(duì)圖進(jìn)行著色，數(shù)據(jù)類型為整型，用不同的數(shù)字表示不同的顏色。本程序的時(shí)間復(fù)雜度為n2。運(yùn)行測(cè)試：五、體會(huì)與自我評(píng)價(jià)本次題目是我選擇的圖操作的一個(gè)問(wèn)題，設(shè)計(jì)到圖的鄰接頂點(diǎn)的訪問(wèn)和圖的遍歷。圖的存儲(chǔ)結(jié)構(gòu)我選擇的是矩陣的形式，在遍歷的時(shí)候是從第一條邊開(kāi)始，查詢這邊