四色问题.txt

四色问题

地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。

void  MapColor(AdjMatrix  C)

        //以邻接矩阵C表示的n个国家的地区涂色

      {int s[];   //栈的下标是国家编号，内容是色数

       s[1]=1；   //编号01的国家涂1色

       i=2;j=1;   //i为国家号，j为涂色号

       while (i<=n)

         {while (j<=4 && i<=n)

            {k=1;  //k指已涂色区域号

             while (k<i && s[k]*C[i][k]!=j) k++;  //判相邻区是否已涂色

             if (k<i) j=j+1;      //用j+1色继续试探

             else {s[i]=j;i++;j=1;}//与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探

            }

          }//while (j<=4 && i<=n)

       if (j>4) {i--; j=s[i]+1;}  //变更栈顶区域的颜色。

      }//while   }//结束MapColor