地圖著色問題實驗報告文檔

算法設(shè)計與分析課程設(shè)計題目：地圖著色問題文檔：物聯(lián)網(wǎng)工程學(xué)院物聯(lián)網(wǎng)工程專業(yè)

一、問題描述：地圖著色問題設(shè)計要求:已知中國地圖,對各省進行著色,要求相鄰省所使用的顏色不同,并保證使用的顏色總數(shù)最少.二、概要設(shè)計（流程圖）步驟：1．已知中國地圖，對各省進行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少；2．將各省進行編號，然后利用無向圖的頂點之間的邊來表示各省的相鄰關(guān)系；3．將各編號進行逐一著色，利用循環(huán)語句遍歷各省，判斷語句判斷是否符合要求；4．演示程序，以用戶和計算機的對話方式進行；5．最后對結(jié)果做出簡單分析及總結(jié)。流程圖.--

-三、源程序#include<stdio.h>#include<stdlib.h>#defineMAXedg100#defineMAX0#defineN4/*著色的顏色數(shù)*/intcolor[30]={0};/*來存儲對應(yīng)塊的對應(yīng)顏色*/typedefcharvextype;typedefintadjtype;typedefstruct/*定義圖*/{vextypevexs[MAXedg];/*存放邊的矩陣*/adjtypearcs[MAXedg][MAXedg];/*圖的鄰接矩陣*/intvnum,arcnum;/*圖的頂點數(shù)和邊數(shù)*/}Graph;intLocateVex(GraphG,charu){inti;for(i=1;i<=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){exit(1);}.--

-return0;}voidCreateGraph(Graph&G)/*輸入圖*/{inti,j,k,w;vextypev1,v2;輸入圖的頂點數(shù)和邊數(shù)getchar();輸入圖的各頂點：for(i=1;i<=G.vnum;i++){getchar();}for(i=0;i<=G.vnum;i++)for(j=0;j<=G.vnum;j++)G.arcs[i][j]=MAX;輸入邊的兩個頂點和權(quán)值(均用1表示for(k=0;k<G.arcnum;k++){i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}.--

-}voidPrintGraph(GraphG)/*輸出圖的信息*/{inti,j;圖的各頂點：for(i=1;i<=G.vnum;i++)圖的鄰接矩陣：for(i=1;i<=G.vnum;i++){for(j=1;j<=G.vnum;j++)}}intcolorsame(ints,GraphG)/*判斷這個顏色能不能滿足要求*/{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++)}voidtrycolor(ints,GraphG)/*s為開始圖色的頂點，本算法從1開始*/{inti;if(s>G.vnum)/*遞歸出口*/{output(G);exit(1);}else{for(i=1;i<=N;i++)/*對每一種色彩逐個測試*/{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);/*進行下一塊的著色*/}}}intmain(){GraphG;CreateGraph(G);.--

trycolor(1,G);return0;}四、運行主要結(jié)果界面貼圖1、中國地圖簡略圖2、取地圖一部分進行測試有6個頂點，8條邊。各點相鄰情況為：a-b,a-e,b-c,b-d,b-e,c-d,d-ee-f

3、運行結(jié)果五、總結(jié)對中國地圖著色即圖著色問題，用m種顏色來為無向圖著色，其中頂點個數(shù)為n。為此，用一個n元組來描述圖的一種著色。在這種著色中，所有相鄰的頂點都不會具有相同的顏色，這種著色就是有效著色。根據(jù)這種思想編寫中國地圖著色算法，算法主要使