<span style="font-family: 'Microsoft YaHei'; background-color: rgb(255, 255, 255);">1.问题描述:</span>
给定无向连通图G和m种不同的颜色。用这些颜色为图G的所有顶点着色,每个顶点着一种颜色。每条边的2个顶点颜色不同。称为图的m着色。
求有多少种方法为图可m着色。
示例:
该无向连通图每个顶点有3种着色方式,试求图的m着色方案有几种
![](https://img-blog.csdn.net/20151226204551329)
有6种
具体过程在下面
2.算法设计:
很明显,约束条件为相邻顶点的颜色不同。
条件:相邻 & 颜色不同
图的临接矩阵为a[][],
数组x[]存放可行解
设置约束函数
bool Ok(int t)
{
for(int j=1;j<t;j++)
if(a[t][j]) //a是图的临接矩阵,判断顶点是否相邻
if(x[j]==x[t])//x记录当前解,x[i]存放第i个顶点的颜色值
return false; //如果相邻两个顶点的颜色相同,则返回false
return true; //否则返回true
}
3.代码:
#include<iostream>
#include<stdio.h>
using namespace std;
int x[100],m,a[100][100];
int sum=0,n;
bool Ok(int t)
{
for(int j=1;j<t;j++)
if(a[t][j]) //a是图的临接矩阵,判断顶点是否相邻
if(x[j]==x[t])//x记录当前解,x[i]存放第i个顶点的颜色值
return false; //如果相邻两个顶点的颜色相同,则返回false
return true; //否则返回true
}
void Backtrack(int t)
{
int i;
if(t>n)//若搜索结束,即果所有顶点着色完毕
{
sum++;
printf("第%d种方案:\n",sum);
for(i=1;i<=n;i++)
cout<<x[i]<<' ';
cout<<endl;
}
else//否则进行判断
{
for(i=1;i<=m;i++)
{
x[t]=i;
if(Ok(t)) //判断顶点t是否与相邻的已经着色的顶点颜色相同,没有相同颜色,则执行下一次查找
Backtrack(t+1);
}
}
}
int main()
{
int i,j;
cout<<"请输入颜色数:"<<endl;
cin>>m;
cout<<"请输入顶点数:"<<endl;
cin>>n;
cout<<"请输入临接矩阵:"<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>a[i][j];
cout<<endl;
cout<<"每个顶点的颜色方案:"<<endl;
Backtrack(1);
return 0;
}
/*
测试数据:
3
5
0 1 1 0 0
1 0 1 1 1
1 1 0 1 0
0 1 1 0 1
0 1 0 1 0
*/