武汉理工大学：《软件技术基础》课程教学资源（PPT课件）例、地图四染色问题

例、地图四染色问题 四染色”定理是计算机科学中著名的定理之 使地图中相邻的国家或行政区域不重色,最少可用四种 颜色对地图着色。 思想:对每个行政区编号: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(J4)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 ( I4) 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(k4)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 ( I4) 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(k4)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 ( I4) 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

Void macolor(int Ru[Lint n, int s[l) 1234567 s[1]=1;/1号区域染1色 =2;J=1;∥/为区域号,为染色号 000 101 000 while(k4)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 ( I4) 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=2 k=1

Void macolor(int Ru[Lint n, int s[l) 1234567 s[1]=1;/1号区域染1色 =2;J=1;∥/为区域号,为染色号 0000 000 while(k4)THEN{|=-1;J=s[]+1 k=2

Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I4) 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=2 k=2

Void macolor(int Ru[Lint n, int s[l) 1234567 s[1]=1;/1号区域染1色 =2;J=1;∥/为区域号,为染色号 0000 234567 0110 while(k4)THEN{|=-1;J=s[]+1 k=2

Void mapcolor(int R[][],int n,int s[]) { s[1]=1; // 1号区域染1色 I=2; J=1; // I为区域号，J为染色号 while ( I4) 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 I=3,J=1 k=2 2

Void macolor(int R[I,int n, int s) 1234567 =2;=1;∥/为区域号,为染色号 000 101 000 while(k4)THEN{|=-1;J=s[]+1

Void mapcolor(int R[][],int n,int s[]) { …… I=2; J=1; // I为区域号，J为染色号 while ( I4) 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 2 2 3 4 1 2 3 4 5 6 7 I=6,J=1 k=1

Void macolor(int R[I,int n, int s) 1234567 1=6;J=1;∥/为区域号,为染色号 0000 while(k4)THEN{|=-1;J=s[]+1

Void mapcolor(int R[][],int n,int s[]) { …… I=6; J=1; // I为区域号，J为染色号 while ( I4) 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 2 2 3 4 1 2 3 4 5 6 7 I=6,J=2 k=1