演算法設計與分析課程設計
題目： 地圖著色問題
文件 物聯網工程學院物聯網工程專業
學號學生姓名
班級二〇一三年十二月
一、問題描述：
地圖著色問題
設計要求:已知中國地圖,對各省進行著色,要求相鄰省所使用的顏色不同,並保證使用的顏色總數最少.
二、概要設計（流程圖）
步驟：1．已知中國地圖，對各省進行著色，要求相鄰省所使用的顏色不同，並保證使用的顏色總數最少；
2．將各省進行編號，然後利用無向圖的頂點之間的邊來表示各省的相鄰關係；
3．將各編號進行逐一著色，利用迴圈語句遍歷各省，判斷語句判斷是否符合要求；
4．演示程式，以使用者和計算機的對話方式進行；
5．最後對結果做出簡單分析及總結。
流程圖三、源程式
#include
#include
#define maxedg 100
#define max 0
#define n 4 /*著色的顏色數*/
int color[30]=;/*來儲存對應塊的對應顏色*/
typedef char vextype;
typedef int adjtype;
typedef struct /*定義圖*/
graph;
int locatevex(graph g,char u)
if(i==g.vnum)
return 0;
}void creategraph(graph &g) /*輸入圖*/
for(i=0;i<=g.vnum;i++)
for(j=0;j<=g.vnum;j++)
g.arcs[i][j]=max;
printf("輸入邊的兩個頂點和權值(均用1表示):\n");
for(k=0;k
}void printgraph(graph g) /*輸出圖的資訊*/
}int colorsame(int s,graph g)/*判斷這個顏色能不能滿足要求*/
return flag;
}void output(graph g)/*輸出函式*/
void trycolor(int s,graph g)/*s為開始圖色的頂點，本演算法從1開始*/
else
}}int main()
四、執行主要結果介面貼圖
1、中國地圖簡略圖
2、取地圖一部分進行測試
有6個頂點，8條邊。
各點相鄰情況為：a-b ,a-e ,b-c ,b-d ,b-e ,c-d, d-e e-f
3、執行結果
五、總結
對中國地圖著色即圖著色問題，用m種顏色來為無向圖著色，其中頂點個數為n 。為此，用乙個n元組來描述圖的一種著色。在這種著色中，所有相鄰的頂點都不會具有相同的顏色，這種著色就是有效著色。
根據這種思想編寫中國地圖著色演算法，演算法主要使用回溯法。根據演算法執行，可以看出，無論有多少點，點與點之間怎樣相鄰，都只需要4種顏色就可以完成著色。
通過此次對中國地圖著色問題的**，我更好更深入了學習了著色問題中回溯法的運用，在課堂上學習的理論知識只有運用到實踐裡才能被更好的掌握。
地圖學實驗報告
地圖學課程實驗報告 地圖學課程實驗報告 地圖學實驗成績評分標準 實驗一地形圖和幾種專題地圖認識 1 閱讀1 10000地形圖1幅並總結地圖內容30分 2 閱讀1 50000地形圖1幅並總結地圖內容30分 3 閱讀自然地理專題圖1種並總結地圖內容20分 4 閱讀社會經濟專題圖1種並總結地圖內容20分。...
地圖學實驗報告書
專業姓名 學號組次 華北水利水電學院地理資訊系統實驗室 2010年8月 實驗一地圖投影及其變換 實驗名稱專業 班級姓名 學號實驗組號 實驗日期 1 實驗目的 2 實驗使用的基礎資料和儀器 3 操作步驟 4 實驗結果 5 成績評定 實驗二地圖數位化 實驗名稱專業 班級姓名 學號實驗組號 實驗日期 1 ...
n皇后問題演算法實驗報告
演算法分析與設計實驗報告 實驗內容 n皇后問題 實驗時間 2013.12.3 姓名 杜茂鵬 班級 計科1101 學號 0909101605 一 實驗內容及要求 在n n格的棋盤上放置彼此不受攻擊的n個皇后，按照西洋棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。2 實驗目的 1.鞏固...