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

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

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

2、簡單分析及總結(jié)。流程圖.---三、源程序#include#include#defineMAXedg100#defineMAX0#defineN4/*著色的顏色數(shù)*/intcolor[30]={0};/*來存儲(chǔ)對應(yīng)塊的對應(yīng)顏色*/typedefcharvextype;typedefintadjtype;typedefstruct/*定義圖*/{vextypevexs[MAXedg];/*存放邊的矩陣*/adjtypearcs[MAXedg][MAXedg];/*圖的鄰接矩陣*/intvnum,arcnum;/*圖的頂

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

4、"輸入圖的各頂點(diǎ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("輸入邊的兩個(gè)頂點(diǎn)和權(quán)值(均用1表示):");for(k=0;k

5、v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}.---}voidPrintGraph(GraphG)/*輸出圖的信息*/{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("");

6、}}intcolorsame(ints,GraphG)/*判斷這個(gè)顏色能不能滿足要求*/{inti,flag=0;for(i=1;i<=s-1;i++)/*分別與前面已經(jīng)著色的幾塊比較*/if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}returnflag;}voidoutput(GraphG)/*輸出函數(shù)*/.---{inti;for(i=1;i<=G.vnum;i++)printf("%d",color[i]);printf("");}voidtrycolor(ints,GraphG)

7、/*s為開始圖色的頂點(diǎn)，本算法從1開始*/{inti;if(s>G.vnum)/*遞歸出口*/{output(G);exit(1);}else{for(i=1;i<=N;i++)/*對每一種色彩逐個(gè)測試*/{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);/*進(jìn)行下一塊的著色*/}}}intmain(){GraphG;CreateGraph(G);.---PrintGraph(G);printf("著色方案:");trycolor(1,G);return0;}四、運(yùn)行主要結(jié)果界面貼圖1、中國地圖簡略圖

8、2、取地圖一部分進(jìn)行測試有6個(gè)頂點(diǎn)，8條邊。各點(diǎn)相鄰情況為：a-b,a-e,b-c,b-d,b