例、地图四染色问题 四染色”定理是计算机科学中著名的定理之 使地图中相邻的国家或行政区域不重色,最少可用四种 颜色对地图着色。 思想:对每个行政区编号:1-7 对颜色编号;a、b、c、d; 从第一号行政区开始逐一染色,每一个区域逐次用四种 颜色进行试探,着所取颜色与周围不重,则用栈记下来 该区域的色数,否则依次用下一色数进行试探。若出现 a-d均与周围发生重色,则需退栈回溯,修改当前栈顶 的色数
例、 地图四染色问题 “四染色”定理是计算机科学中著名的定理之一。 使地图中相邻的国家或行政区域不重色，最少可用四种 颜色对地图着色。 思想：对每个行政区编号：1-7 对颜色编号；a、b、c、d； 从第一号行政区开始逐一染色，每一个区域逐次用四种 颜色进行试探，若所取颜色与周围不重，则用栈记下来 该区域的色数，否则依次用下一色数进行试探。若出现 a-d均与周围发生重色，则需退栈回溯，修改当前栈顶 的色数
思想:对每个行政区编号:1-7 对颜色编号;a、b、c、d; a粉色b黄色 思考: c红色d绿色 算法? 需何种数据结构?
思想：对每个行政区编号：1-7 对颜色编号；a、b、c、d； a 粉色 b 黄色 c 红色 d 绿色 思考： 算法？ 需何种数据结构？
Void macolor(int RIO,int n, int sO) 1#粉色 s[1]=1;∥/1号区域染1色 2#黄色 =2;上=1;∥/为区域号,」为染色号 (1) (3) while( k=n) 3#红色 whle(J<=4)&&(<=n) (6) 4#绿色 k=1;//k表示已经着色的区域号 while(( k<l&&(s(K]+R[KJl=J)) K=K+1;∥若不相邻,或若相邻且不重色,对下一个区域判断。 IF(K<I) s[1:7] THEN J=J+1 ELSE{s[;l=H+1;上1;} 1234567 IF(J>4)THEN{|=-1;上=s叮]+1 12|23a4 R[1:7,1:7] 12243 1234567 10111110 21000010 1001100 1010110 123 510 23243 61101100 70000000 2|32|43|1
0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 R [ 1: 7 , 1 : 7 ] 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I<=n) { while(( J<=4)&&(I<=n)) { k=1; // k表示已经着色的区域号 while(( K<I)&&(s[K]R[I,K]!=J)) K=K+1; // 若不相邻，或若相邻且不重色，对下一个区域判断。 IF (K<I) THEN J=J+1 ELSE{ s[I]=J; I=I+1; J=1; } } IF (J>4) THEN { I=I-1; J=s[I]+1 } } (2) (1) (4) (5) (6) (7) (3) 1# 粉色 2# 黄色 3# 红色 4# 绿色 1 2 3 2 1 2 3 1 2 2 4 3 1 2 3 2 4 3 1 2 3 2 4 1 2 3 2 4 3 1 1 2 2 3 4 1 2 3 4 5 6 7 S [ 1 : 7 ]
Void macolor(int Ru[Lint n, int s[l) 1234567 s[1]=1;∥/1号区域染1色 =2;J=1;∥/为区域号,为染色号 0000 234567 0110 while(k<=n) 000 01 { while((J<=4)&&(|<=n) 000 110 k=1;/k表示已经着色的区域号 101100 0000000 while((k<l&&s[k]*RLk=J) k=k+1;∥/若不相邻,或若相邻且不重色,对下一个区域判断。 IF(K<∥/相邻且重色 1234567 THEN J=J+1 ELSE{s[]=;=+1;J=1;相邻且不重色 IF(J>4)THEN{|=-1;J=s[]+1
Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I<=n) { while(( J<=4)&&(I<=n)) { k=1; // k表示已经着色的区域号 while(( k<I)&&(s[k]R[I,k]!=J)) k=k+1; // 若不相邻，或若相邻且不重色，对下一个区域判断。 IF (K<I) //相邻且重色 THEN J=J+1 ELSE{s[I]=J; I=I+1; J=1; }//相邻且不重色 } IF (J>4) THEN { I=I-1; J=s[I]+1 }} } 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7
Void macolor(int Ru[Lint n, int s[l) 1234567 s[1]=1;/1号区域染1色 =2;J=1;∥/为区域号,为染色号 0000 000 while(k<=n) 0 { while((J<=4)&&(|<=n) 10 k=1;/k表示已经着色的区域号 6 10110 0000 000000 while((k<l&&s[k]*RLk=J) k=k+1;∥若不相邻,或若相邻且不重色,对下一个区域判断 IF(K<∥/相邻且重色 1234567 THEN J=J+1 ELSE{s[]=;=+1;J=1;相邻且不重色 k=1 I=2,J=1 IF(J>4)THEN{|=-1;J=s[]+1
Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I<=n) { while(( J<=4)&&(I<=n)) { k=1; // k表示已经着色的区域号 while(( k<I)&&(s[k]R[I,k]!=J)) k=k+1; // 若不相邻，或若相邻且不重色，对下一个区域判断。 IF (K<I) //相邻且重色 THEN J=J+1 ELSE{s[I]=J; I=I+1; J=1; }//相邻且不重色 } IF (J>4) THEN { I=I-1; J=s[I]+1 }} } 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 I=2,J=1 k=1