算法设计与分析课件-回溯法-图的m着色问题

算法设计与分析第五章回溯法目录5.1搜索概述回溯法算法框架5.25.5n皇后问题0-1背包问题5.3作业调度问题5.4图的m着色问题5.65.6图的m着色问题m图着色问题-相关概念：给定无向连通图G=(V,E)和m种不同颜色。用这些颜色为图G的各个顶点着色，每个顶点着一种颜色。如果有一种着色法使G中有边相连的两个顶点着不同颜色，则称该图是m可着色的。12345问题描述：图的m着色问题

(GraphColoringProblem,GCP)是对于给定图G和m种颜色，找出所有不同的着色方法。5.6图的m着色问题求解步骤：问题的解空间：解空间形式为(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个顶点着第xi号颜色。m种颜色的色号组成的集合为S={1,2…,m}。xi∈S，i=1,2,…,n。解空间的组织结构：问题的解空间组织结构是一棵满m叉树，树的深度为n。解空间搜索（剪枝函数）：约束条件：相邻顶点着不同的颜色。限界条件：无。搜索过程：回溯法。5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A12345GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A2345ABX1=11GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A345ABX1=121GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A345ABX1=121ABCX1=1X2=2GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A45ABX1=121ABCX1=1X2=23ABCX1=1X2=2DX3=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A5ABX1=121ABCX1=1X2=23ABCX1=1X2=2DX3=34ABCX1=1X2=2DEX4=1X3=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)21345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)ABCX1=1X2=2DX3=3EX4=1FX5=312345GX2=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345GX2=3ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345GX2=3ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2IX4=1GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345GX2=3ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2IX4=1JX5=2GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)GX2=312345ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2IX4=1JX5=2KX1=2LMPQNORSX2=1X3=3X3=1X4=2X4=2X5=3X5=1X2=3GCP示例5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)GX2=312345ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2IX4=1JX5=2KX1=2LMPQNORSX2=1X3=3X3=1X4=2X4=2X5=3X5=1X2=3TX1=3GCP示例5.6图的m着色问题12345GCP示例5.6图的m着色问题GCP算法设计数据结构

数组x：存储每个结点的着色；二维数组a：存储图,即边的邻接矩阵；

coloring()函数判断第i个结点着第t种颜色是否可行；搜索策略回溯法搜索需要定义一个数据结构存储满m叉树吗？5.6图的m着色问题GCP算法的伪代码backtrack-gcp(t)//t为搜索层

ift>nthenoutput(x);//x[1..n]存放问题的解else

fori1tomdo//试探每一种颜色x[t]i;ifcoloring(t)then

backtrack-gcp(t+1);coloring(k)forj1tok-1do

ifa[k][j]!=0&&x[j]=x[k]do//邻接且着相同的颜色