中國地圖四色染色問題

中國地圖四色染色問題

問題描述

將中國地圖用四種不同的顏色紅、藍、綠、黃來染色，要求相鄰的省份染色不同，

問題分析

本文將中國地圖的34個省、直轄市、自治區、特別行政區、、、行政區則問題轉化為圖論中的染色問題。由于海南、省不任何省份相鄰，如果除海南、外如果n種染色方法，加上海南和臺灣省后，4*4*n種染色方法?？紤]除海南和臺灣后的32的染色方法。地圖染色方法

采用分開和臺灣省的分析方法，的原因是除海南和臺灣后的32，組成一個聯通圖，海南省和臺灣省不和任何其它省份鄰接。另一方面，建立一個聯通圖模型后，染色問題用深度優先遍歷算法DFS，廣度算法BFS解決，該方法的時間復雜度較高，暴力法，考慮兩個省份可以減少計算機處理此問題的時間。采用DFS來解決這個染色問題。

3.1 簡介

算法圖的一種的深度遍歷算法，即按照的地方遍歷一個圖，到一個分支的盡頭，返回到最近一個未被遍歷的結點，深度遍歷。

的具體步驟可為下：

所有結點為“未”標記。

起始結點，標記為“訪問”標記

始結點入棧

若棧為空，；若棧不為空，棧頂元素，該元素存在未被訪問的頂點，輸出一個鄰接頂點，置為“訪問”狀態，；，元素退出棧頂。

3.2 中的DFS算法設計我們先對結點染色，用從該結點出發，遍歷該圖，的下一結點顏色染為與之相鄰的結點不同的顏色即可。該結點無法染色則回到上一個結點重新染色，所有的結點都被染色即可。統計染色種數。

問題的算法代碼描述如下：

_DFS(當前染色結點):

i in 所有顏色

{while j的已染色鄰接點

j相鄰點被染i顏色

并break標記

{

當前結點為i

if 當前結點為最后一個結點

else

color_DFS(next)

｝

}

3.3 數據結構設計實現DFS染色算，需要設計的數據結構。圖的結點不多，只有32，采用圖的鄰接矩陣來存儲該圖，為map[33][33]，ma[0]不存儲數據，兩結點i相鄰，[i][j]=1，否則[i][j]=0。

便于計算機編程，將每一個地名用相應結點號表示，1：2:"西藏",3:"青海",4:"甘肅",5:"內蒙古",6:"寧夏",7:"黑龍江",8:"吉林",9:"遼寧",10:"河北",11:"北京",12:"山西",13:"陜西",14:"山東",15:"天津",16:"河南",17:"安徽",18:"江蘇",19:"上海",20:"浙江",21:"福建",22:"江西",23:"廣東",24:"湖南",25:"湖北",26:"重慶",27:"四川",28:"貴州",29:"云南",30:"廣西",31:"香港32:"澳門"。

新疆和西藏相鄰，我們就可以用map[1][2]=1。

地，顏色我們也可以用一個數字來表示，在這里，數字來代表顏色，比如1-2-藍、3-綠、4-黃。

語言代碼實現

#include

#include

using namespace std;

int map[33][33];

int vis[33];

int n,m;

long long cnt;//染色方法設置為long long防止溢出

void init_map()

{

map[1][2]=map[2][1]=1;//表示新疆和西藏連通

map[1][3]=map[3][1]=1;

map[1][4]=map[4][1]=1;

map[2][3]=map[3][2]=1;

map[2][27]=map[27][2]=1;

map[2][29]=map[29][2]=1;

map[3][4]=map[4][3]=1;

map[3][27]=map[27][3]=1;

map[4][5]=map[5][4]=1;

map[4][6]=map[6][4]=1;

map[4][13]=map[13][4]=1;

map[4][27]=map[27][4]=1;

map[5][6]=map[6][5]=1;

map[5][7]=map[7][5]=1;

map[5][8]=map[8][5]=1;

map[5][9]=map[9][5]=1;

map[5][10]=map[10][5]=1;

map[5][12]=map[12][5]=1;

map[5][13]=map[13][5]=1;

map[6][13]=map[13][6]=1;

map[7][8]=map[8][7]=1;

map[8][9]=map[9][8]=1;

map[9][10]=map[10][9]=1

總結

以上是生活随笔為你收集整理的中国地图着色问题c语言,中国地图四色染色问题.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。