地圖著色演算法c語言_數據結構C語言四染色定理

A. 數據結構c語言四染色定理

下面是用的c++描述的：涉及到類的有關知識。你不知道的話我可以幫你改為c語言描述。不過需要時間（這個星期之內），我最近比較的忙。反正你加了分，你就慢慢等吧！不好意思，我最近太忙了，沒時間給你改。再加點分讓別人給你回復吧！
class color{
friend int mcoloring(int,int,int * *);
private:
bool OK(int k);
void Backtrack(int t）；
int n,//圖的定點數
m,//可用顏色數
**a,//圖的臨接矩陣
*x;//當前解
long sum;//當前已找到的可m著色方案數
};
bool color::OK(int k)
{ //檢查顏色的可用性
for(int j=1;j<=n;j++)
if((a[k][j]==1)&&(x[j]==x[k]))return false;
return true ;
}
void color::Backtrack(int t)
{
if(t>n){
sum++;
for(int i=1;i<=n;i++)
cout<<x[i]<<" ";
cout<<endl;
}
else for(int i=1;i<=m;i++)
{ x[t]=i;
if(OK(t))Backtrck(t+1);
x[t]=0;
}
}
int mcoloring (int n,int m,int **a）
｛color X;
//初始化
X.n=n;
X.m=m;
X.a=a;
X.sum=0;
int *p=new int [n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete []p;
return X.sum;
}

B. 地圖著色問題C/C++

從一個省開始，給它塗上任意一種顏色1，遍歷它旁邊的省份，塗上與已經塗色並於他相鄰的省份不同的顏色就行了。
理論上4種顏色就夠了.地圖的四色問題嘛!
可能會有多組解。用遞歸（dfs)就可以輸出所有解了。

地圖著色演算法C語言源代碼
前面我寫了一個地圖著色（即四色原理）的C源代碼。

寫完以後想了一下，感覺還不完善，因為從實際操作的角度來考慮，四種可用的顏色放在旁邊，不同的人可能會有不同的選擇順序，另外，不同的人可能會選擇不同的城市作為著色的起點，而當時的程序沒有考慮這個問題。於是，把程序修改為下面的樣子，還請同行分析並指出代碼中的不足之處：

＃i nclude <stdio.h>
#define N 21
int allcolor[4];/*可用的顏色*/

int ok(int metro[N][N],int r_color[N],int current)
{/*ok函數和下面的go函數和原來的一樣,保留用來比較兩種演算法*/
int j;
for(j=1;j<current;j++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0;
return 1;
}

void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i;
if(current<=sum)
for(i=1;i<=4;i++)
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1);
return;
}
}
}

void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有編號看作一個環*/
if(i==0)/*城市號從1開始編號,故跳過0編號*/
continue;
else
for(j=0;j<4;j++)
{
r_color[i]=allcolor[j];/*選取下一種顏色,根據allcolor中顏色順序不同，結果不同*/
for(k=1;k<i;k++)/*檢查是否有沖突，感覺還可以改進，如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}

void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;/*著色的起點*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*選色順序，順序不同，結果不同*/
start=1;
/* clrscr();*/
printf("\nAll color is:\n");
for(i=0;i<4;i++)/*當前選色順序*/
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i<=20;i++)
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start);
for(i=1;i<=20;i++)
printf("%3d",t_color[i]);
}

說是人性化著色，其實還有一個問題沒有考慮，那就是操作員跳躍式著色，就像大家玩「掃雷」游戲一樣。其實也容易實現，可以像定義選色順序一樣定義著色順序。

C. c# 地圖四染色

很麻煩的演算法題，分有點少........

嘖，分還是少........算了，給你寫個簡單的把

using System;
using System.Collections.Generic;

namespace 四色猜想
{
public class FourColor
{
public static void Run(int aeraNumeric)
{
//為了偷懶，沒有使用二維矩陣而是直接用了棧，即X的最大相鄰數為2即X-1和X+1，實際上2個顏色就夠用了....
//實例化棧
Stack<Aera> AeraStack = new Stack<Aera>(aeraNumeric);
//演示演算法，使用隨機顏色
Random RandomColor = new System.Random();

for (int i = 0; i < aeraNumeric; i++)
{
//初始化Aera並入棧
Aera MyAera = new Aera((i + 1).ToString(), (Publicenum.FourColor)(RandomColor.Next(4)));
//入棧
if (AeraStack.Count == 0)
{
AeraStack.Push(MyAera);
continue;
}
Aera TestAera = AeraStack.Peek();
if (TestAera.AeraColor == MyAera.AeraColor)
{
int j = 0;
while (j < 5)
{
if (j == 4)
{
throw new InvalidOperationException("超出4色范圍!");
}
Publicenum.FourColor TestColor = (Publicenum.FourColor)j;
if (TestAera.AeraColor == TestColor)
{
j++;
continue;
}
else
{
MyAera.AeraColor = TestColor;
break;
}

}
}
AeraStack.Push(MyAera);
}

//輸出結果
while (AeraStack.Count != 0)
{
Aera OutputAera = AeraStack.Pop();
Console.WriteLine("Name:{0},Color:{1}", OutputAera.AeraName, OutputAera.AeraColor);
}
Console.ReadLine();
}
}

public class Aera
{
public string AeraName { get; set; }
public Publicenum.FourColor AeraColor { get; set; }

public Aera(string aeraName, Publicenum.FourColor aeraColor)
{
AeraName = aeraName;
AeraColor = aeraColor;
}
}

public class Publicenum
{
public enum FourColor
{
A, B, C, D
}
}
}

控制台程序，調用時輸入區域個數如 FourColor.Run(73);

D. 地圖著色問題源程序C++語言（演算法設計與分析）急求

E. C語言編程地圖著色

書上有嘛

F. 求我描述的地圖填色問題詳解(100分,只求詳盡)

最少填色數量,這個似乎不用證明了吧.最少4色.
以下是李寬證明法:
證明：

首先進行抽象處理:有顏色點表示地區，連線表示相鄰及版圖走向。

因為地圖為平面，地區版圖不可相疊覆蓋。

所以連線不能交叉。

因為連線兩端顏色不同。

所以兩兩相連的幾個點顏色各不相同。

所以N個點兩兩相連共需N種顏色。

至此，四色問題轉化為：在連線不允許交叉的前提下，最多有4個點可實現兩兩相連。也就是說，不可能有更多點兩兩相連，也就不可能出現更多色。

點數為1、2、3時均成立。由於線的形狀，點的位置不影響相鄰關系，故點數為3時兩兩相連可畫成三角形。點數為4時，最終均可化為三角形內含有一點且該點與三頂點分別相連的形式。即有一點被三點封閉。

點數為5時，容易發現，無論第五點放在平面什麼位置，都無法實現5個點在連線不交叉的前提下兩兩相連。（關鍵）

因為連線過程是遞進的。即必然先滿足三點兩兩相連，後滿足四點兩兩相連，隨後第五點。而已知第五點連線失敗，點數更多也就不可能實現了。

環狀地區，可抽象為環。環本身是封閉的。相對於環外點和環，環可視為點。在環內加點連線，最終可形成封閉區

點和環均定義為元素，欲用最少色塗最多元素，同時欲用更多色，必產生封閉區域。再用元素最少情況下，三點三線、一點一環兩線、兩點外一環三線為三種情況。在此基礎上加點，最多四元素兩兩相連，最多為3+1=4色。（易操作）

無論多少元素建立連線，都不會出現多於四點兩兩相連情況。故最多四色。

由此，四色問題證畢。

G. 四色問題C語言怎麼解決

思路：建立數據結構，錄入數據內容，遍歷著色，輸出第一個可行的著色方案。

下面就四個方面詳細分析一下

首先分析數據結構：

對於地圖，一個區塊包含一個唯一編號數據（這個編號可以是地名，也可以是數字）用來區分該區塊和其他區塊的不同

另外要著色，還要考慮該區塊和其他區塊連接的情況

最後就是區塊本身的顏色

通過上面的分析，即可建立如下數據結構：

structarea{
intnID;//這里以數字替代名稱，作為地塊的唯一標識
intnColor;//用1,2,3,4表示不同的顏色，用0表示還沒有著色
area*pNei;//鄰接的區塊
intnNei;//鄰接區塊的數量
};

然後需要錄入數據，這個請依據具體的地圖進行處理，撰寫相應的錄入函數，填入上面的數據結構

假設錄好的數據如下：

structareacity[64];//假設已經錄制好了數據，初始所有城市顏色都為0

數據錄好後，我們可以如下方式進行遍歷，嘗試著色

遍歷分為個模塊：一個是遍歷模塊，一個是校驗模塊

校驗模塊依序檢查所有的城市和其鄰接城市是否存在同色的情況，是則返回false，否則返回true

遍歷模塊則逐個城市進行上色嘗試

可以考慮遞歸

下面給一個遞歸的示例：

檢測模塊：

boolisOk(){
for(inti=0;i<64;i++)//假設有64個城市，其初始值和城市關系已經錄制完畢
{
for(intj=0;j<city[i].nNei;j++){
if(nColor==city[i].pNei[j].nColor)
returnfalse;
}
}
returntrue;
}

遍歷遞歸模塊：

booladdcity(intnIndex){
if(nIndex>=64)returntrue;//所有城市都著色了，則返回成功
for(inti=1;i<=4;i++){
city[nIndex].nColor=i;
if(isOk()){//本城市的顏色找到了
if(addcity(nIndex+1)==true){//找下一個城市的顏色
returntrue;
}else{//無法為下一個城市著色
continue;//更改本城市顏色
}
}
}
returnfalse;//沒有一個顏色可行，返回上一級，重新尋找
}

調用的時候可以採用下面的方式：

if(addcity(0)==false){
printf("無法找到答案，四色定理錯誤！
");
}else{
printf("找到了答案，城市和著色結果如下：
");
for(inti=0;i<64;i++){
printf("city%03dcolor%d
",city[i].nID,city[i].nColor);
}
}

H. c++，怎麼解決地圖著色問題

地圖著色可以使用回溯的方法進行解決。

遞歸描述如下：

在前面n-1個節點都合法的著色之後，開始對第n個節點進行著色。

這時候枚舉可用的m個顏色，通過和與它相鄰的節點的顏色，來判斷這個顏色是否合法。

如果找到那麼一種顏色使得第n個節點能夠著色，那麼說明m種顏色的方案是可行的。

//用於判斷當前節點上塗上這個顏色可不可行，與其鄰接節點的顏色做判斷，這里用鄰接表來存儲圖的信息
boolisOk(intstep)
{
vector<int>::iteratoriter;
for(iter=input[step].begin();iter!=input[step].end();iter++)
{
if(Color[step]==Color[*iter])returnfalse;
}
returntrue;
}
//step表示0->n的節點，color_num是指給color_num的顏色的個數可用
//判斷如果給color_num的顏色的個數是否可行，如果可行返回true,否則false
boolDFS(intstep,intcolor_num)
{
if(step>=n)returntrue;
else
{
inti;
for(i=1;i<=color_num;i++)
{
Color[step]=i;
if(isok(step))
{
if(DFS(step+1,color_num))
returntrue;
}
Color[step]=0;
}
}
returnfalse;
}

I. 急！利用5種不同的演算法，為中國地圖每個省著色，要求相鄰的省份顏色不同，所用的顏色最少！！

這是根據數學史上著名的四色問題，每幅地圖都可以用四種顏色著色，使得有共同代表地形的不同！顏色不代表什麼，主要是為了區分方便，如果用同一種

地圖著色演算法c語言

與地圖著色演算法c語言相關的內容