siranse.c

用c++语言实现的地图四染色算法

#include<iostream.h>
#define MAXSIZE 10
void main(){
void mapcolor(int (*r)[MAXSIZE],int *s,int n);
int b[MAXSIZE];
int a[MAXSIZE][MAXSIZE];
int i,j,n;
int k=0,color=1;
bool zhen=true;
bool zhen1=true;
bool zhen2=true;
for(i=0;i<MAXSIZE;i++)
	for(j=0;j<MAXSIZE;j++)
		a[i][j]=0;
cout<<"请输入要颜色的区域数目"<<endl;
cin>>n;
cout<<"请输入各区域间的关系,相邻输入1,不相邻输入0"<<endl;
for(i=0;i<n;i++){
cout<<"请输入第"<<i+1<<"行数据"<<"  "<<"请输入"<<i+1<<"个数据"<<endl;
for(j=0;j<=i;j++){
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
for(j=0;j<n;j++){
b[j]=0;
}
mapcolor(a,b,n);
}
void mapcolor(int (*r)[MAXSIZE],int *s,int n){
int color ,area,k;
bool zhen=true;
s[0]=1;
area=1;
color=1;
while(area<n){
	while((color<=4)&&(zhen)){//while start
	k=0;
	while((k<area)&&(s[k]*r[area][k]!=color)){
	k++;
	}
	if(k<area){
	color++;
	}
	else{
	s[area]=color;
	area++;
	color=1;
	if(area==n){
	zhen=false;
	}
	}
	}//while end
	if(color>4){
	area-=1;
	color=s[area]+1;
	}
}
cout<<"各区域染色情况如下"<<endl;
for(k=0;k<n;k++)
cout<<"区域 "<<k+1<<":  "<<s[k]<<"色"<<endl;
}