地圖著色問題實(shí)驗(yàn)報告.doc

《地圖著色問題實(shí)驗(yàn)報告.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、算法設(shè)計(jì)與分析課程設(shè)計(jì)題目：地圖著色問題文檔：物聯(lián)網(wǎng)工程學(xué)院物聯(lián)網(wǎng)工程專業(yè)學(xué)號學(xué)生姓名班級二〇一三年十二月8一、問題描述：地圖著色問題設(shè)計(jì)要求:已知中國地圖,對各省進(jìn)行著色,要求相鄰省所使用的顏色不同,并保證使用的顏色總數(shù)最少.二、概要設(shè)計(jì)（流程圖）步驟：1．已知中國地圖，對各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少；2．將各省進(jìn)行編號，然后利用無向圖的頂點(diǎn)之間的邊來表示各省的相鄰關(guān)系；3．將各編號進(jìn)行逐一著色，利用循環(huán)語句遍歷各省，判斷語句判斷是否符合要求；4．演示程序，以用戶和計(jì)算機(jī)的對話方式進(jìn)行；5．最后對結(jié)果做出簡單分析及總結(jié)。流程圖8三、源程序#in

2、clude#include#defineMAXedg100#defineMAX0#defineN4/*著色的顏色數(shù)*/intcolor[30]={0};/*來存儲對應(yīng)塊的對應(yīng)顏色*/typedefcharvextype;typedefintadjtype;typedefstruct/*定義圖*/{vextypevexs[MAXedg];/*存放邊的矩陣*/adjtypearcs[MAXedg][MAXedg];/*圖的鄰接矩陣*/intvnum,arcnum;/*圖的頂點(diǎn)數(shù)和邊數(shù)*/}Graph;intLocateVex(GraphG,charu

3、){inti;for(i=1;i<=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){printf("Erroru!");exit(1);}8return0;}voidCreateGraph(Graph&G)/*輸入圖*/{inti,j,k,w;vextypev1,v2;printf("輸入圖的頂點(diǎn)數(shù)和邊數(shù):");scanf("%d%d",&G.vnum,&G.arcnum);getchar();printf("輸入圖的各頂點(diǎn)：");for(i=1;i<=G.vnum;i++){scanf("%c",&G.vexs[i]

4、);getchar();}for(i=0;i<=G.vnum;i++)for(j=0;j<=G.vnum;j++)G.arcs[i][j]=MAX;printf("輸入邊的兩個頂點(diǎn)和權(quán)值(均用1表示):");for(k=0;k

5、hG)/*輸出圖的信息*/{inti,j;printf("圖的各頂點(diǎn)：");for(i=1;i<=G.vnum;i++)printf("%c",G.vexs[i]);printf("");printf("圖的鄰接矩陣：");for(i=1;i<=G.vnum;i++){for(j=1;j<=G.vnum;j++)printf("%d",G.arcs[i][j]);printf("");}}intcolorsame(ints,GraphG)/*判斷這個顏色能不能滿足要求*/{inti,flag=0;for(i=1;i<=s-1;i++)/*分別與前面已經(jīng)著色的幾塊比較*

6、/if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}returnflag;}voidoutput(GraphG)/*輸出函數(shù)*/8{inti;for(i=1;i<=G.vnum;i++)printf("%d",color[i]);printf("");}voidtrycolor(ints,GraphG)/*s為開始圖色的頂點(diǎn)，本算法從1開始*/{inti;if(s>G.vnum)/*遞歸出口*/{output(G);exit(1);}else{for(i=1;i<=N;i++)/*對每一種色彩逐個測試*/{color[s]

7、=i;if(colorsame(s,G)==0)trycolor(s+1,G);/*進(jìn)行下一塊的著色*/}}}intmain(){GraphG;CreateGraph(G);8PrintGraph(G);printf("著色方案:");trycolor(1,G);return0;}四、運(yùn)行主要結(jié)果界面貼圖1、中國地圖簡略圖2、取地圖一部分進(jìn)行測試有6個頂點(diǎn)，8條邊。各點(diǎn)相鄰情況為：a-b,a-e,b-c,b-d,b-e,c-d,d-ee-f83、運(yùn)行結(jié)