地图染色问题(回溯法)

青旅半醒 2022-08-10 09:19 242阅读 0赞

1.问题描述:

对图G共分成n个顶点,有m种颜色,现在要对其进行作色,要求相邻的顶点不能染相同的颜色.

2.算法设计:

*  对于给定无向连通图G 可用邻接矩阵表示,该邻接矩阵用一个二维数组表示,其中为了直观,第0行和第0列全赋值为0,不参与算法.

如邻接矩阵 a\[i\]\[j\],若a\[1\]\[2\]=1;则表示地图1区域和2区域(相邻)连通,不难知道 a\[2\]\[1\]也为1.  若i,j不相邻,则a\[i\]\[j\] = a\[j\]\[i\]=0.

*  关于不同地图区域的着色,可以用一维数组x\[i\]表示,如: x\[3\]=2; 表示第3块区域着第2号色.

3.解空间:

用一颗高度为n+1的m叉树,即表示每个结点有m种着色选择.

![Center][]

*  用回溯法Backtrack(i) 按深度遍历搜索,当找到第n+1层,即i>n,表示找到一个解决方案,注意只有符合条件查找才会继续.
 *  代码示例:

#include<iostream>
    using namespace std;
    class Color{
    	friend int mColoring(int,int, int **);	//友元函数声明
    private:
    	bool OK(int k);
    	void Backtrack(int t);
    	int n,			//顶点数
    		m,			//颜色数
    		* * a,		//图的邻接矩阵,记录相邻顶点
    		* x;		//当前解, x[2]=3;表示第二个点染3号色
    		long sum;	//记录截至当前解决方案个数
    };
    
    bool Color::OK(int k)//函数定义
    {//查看是否符合条件
    	for(int j=1;j<=n;j++)
    		if( (a[k][j]==1)&&(x[k]==x[j]) )//即第k个和第j个相邻且染同色(在邻接矩阵里有边的点不能染同色)
    			return false;
    	return true;	//此处不可写else 必须走完j,和所有相邻的点检测一遍
    }
    
    void Color::Backtrack(int t)
    {
    	if(t>n){
    		sum++;//解决方案++ 拓展至子结点
    		cout<<"染色方案_"<<sum<<":\t";
    		for (int i = 1; i <=n; i++) //输出解决方案
    			cout<<x[i]<<" ";			
    		cout<<endl;
    	}
    	else 
    		for (int i = 1; i <=m; i++)	//每种颜色都试下
    		{
    			x[t]=i;					//尝试染色
    			if(OK(t))Backtrack(t+1);//if:ok 递归进入下一个
    			x[t]=0;
    		}
    }
    
    //-------------------------------------------------------------
    int mColoring(int n,int m, int **a)	//调用函数
    {
    	Color X;
    	X.n=n;
    	X.m=m;
    	X.a=a;	//邻接矩阵
    	X.sum=0;	//解决方案初始化0
    
    	int *p = new int [n+1];	//当前解初始化;
    	for (int i = 0; i <=n; i++)		//即使第0个不用,亦初始化
    		p[i]=0;
    	X.x = p;	//x指向p 共享一块空间
    	X.Backtrack(1);
    	delete []p;	//删除数组
    	return X.sum;
    }
    //------------------------------------------------------
    void Show_TheMap(int **p, int n)//输出邻接矩阵
    	{
    		int i,j;
    		cout<<"该图邻接矩阵如下:\n";
    		for (i = 1; i <=n; i++)
    			for (j = 1; j <=n; j++)
    			{
    				cout<<p[i][j]<<" ";
    				if(j==n)	cout<<endl;
    			}
    	}
    void main()
    {	
    	int **a = new int *[6];				//第0个不存,只存 邻接矩阵:1-5行 1-5列
    	for (int i = 0; i < 6; i++)
    	{
    		a[i] = new int[6];
    	}
    //邻接矩阵初始化
    	for (int i = 1; i < 6; i++)
    		for(int j=1;j < 6; j++)
    			a[i][j]=1;
    	for(int i=1;i<6;i++)
    		a[i][i]=0;	//对角线初始化为0,其余初始化为1;	此处为测试例子		
    	a[3][5]=a[5][3]=0;a[1][5]=a[5][1]=0;	//表示1-3,5-3不相邻
    
    	Show_TheMap(a,5);
    	cout<<endl;
    	cout<<"共有"<<mColoring(5,4,a)<< " 个染色方案"<< endl;	//调用
    	
    }

程序结果示例:

![20151120092250051][]

![20151120092340770][]

该算法引用自:《计算机算法设计与分析》————电子工业出版社p137-p139

[Center]: /images/20220731/b412dbb38bdf44d2bdacb39eea6b9f61.png
[20151120092250051]: /images/20220731/38937ccf29214ae190304f92bc79827c.png
[20151120092340770]: /images/20220731/7b330ec79df0486b998933cefeea305c.png