实验四回溯法(图的着色问题).pptVIP

实验四 回溯法 — 图的着色问题 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。 地图（map）中地区的相邻关系，在图（graph）中用边表示。 无向图G 【实验内容与要求】 图的着色问题：设G=(V,E)是一连通无向图，有3种颜色，用这些颜色为G的各顶点着色，每个顶点着一种颜色，且相邻顶点颜色不同。试用回溯法设计一个算法，找出所有可能满足上述条件的着色法。 无向图G 0 1 2 3 4 0 0 1 1 0 1 1 1 0 1 0 1 2 1 1 0 1 0 3 0 0 1 0 1 4 1 1 0 1 0 对应这个无向图的状态空间树应该是怎样的？ 是一个完全3叉树，共6层 对应的邻接矩阵 无向图G class MGraph { public: MGraph(int v,int s); void mColoring(int m,int *x); //一维数组x，存放1~n个顶点的颜色 ~MGraph(); private: void NextValue(int k,int m,int *x); void mColoring (int k,int m,int *x); int **a; //二维数组a，存储图的邻接矩阵 int n,e; //n表示图的顶点数，e表示边数 }; 递归回溯： 1. 为x[k]分配一个合法的颜色（即为第k个顶点分配颜色）。 2. 如果x[k]为0,表示当前没有适合的颜色，此方案不可行，返回。 3. 顶点k颜色分配成功后： 3.1如果k=n-1，表示所有顶点分到一个合法的颜色（完全着色）； 输出x数组 3.2否则（还未完全着色）对k+1顶点进行着色（递归，向下一层有哪些信誉好的足球投注网站）； 4. 回到1，寻找下一个可行的方案 void MGraph:: mColoring(int k,int m,int *x) { do { NextValue(k,m,x); //为x[k]分配颜色 if (x[k]==0) break; if (k == n-1) { //得到图G的一种m-着色方案 for (int i=0; in; i++) cout x[i] ; cout endl; } else mColoring(k+1,m,x); //已经对前k个结点分配了颜色，尝试其余结点(部分着色) } while(1); } //x[k]=0表示当前没有适当的颜色，此着色方案不可行 完全着色 void MGraph::NextValue(int k,int m,int *x) { //本函数在[1,m]中为x[k]确定一个值最小的，且不与其邻接点冲突的颜色 //x[k]=0 表示没有可用颜色，颜色从1开始编号 do { x[k]=(x[k]+1) % (m+1); //尝试下一种颜色 if (x[k]==0) return; //已经试完所有颜色，没有可用颜色 for (int j=0; jk; j++) if (a[k][j] x[k] == x[j]) break; //若(i, j)是图的边，且相邻结点k和j颜色相同 //发生冲突，选下一种颜色 if (j==k) return; //成功选择一种颜色返回 }while (1); //循环尝试颜色 } 运行结果： 此图的存储方式：邻接矩阵（n个顶点，n阶方阵） * 应该再搭配解空间数，演示回溯过程。 此图的存储方式：邻接矩阵（n个顶点，n阶方阵） * 应该再搭配解空间数，演示回溯过程。