问题描述

3-着色问题

判定无向图G=(V,E)是否可以用3种颜色着色,可以,请给出着色方案。

问题分析

处理三色问题,我们要考虑到每条边的两个端点颜色需要不同。

采用回溯的方法,对每种结果进行尝试,如果当前颜色不能满足约束条件,则换一种颜色,如果任何颜色尝试任何颜色后,都不满足约束条件,则需要向后退,k<- k-1,同时把尝试颜色的点的颜色清空(c[k] = 0 ) .

如果尝试的颜色满足约束条件,则判断它是否满足解的条件,如果满足,则输出相应颜色分布。否则,则可能为部分解,接下来尝试下一个节点颜色。

算法设计

首先使用按行读文件的方式,从文件获取顶点个数、边的个数以及相应的两 个顶点之间有边。 所花时间为线性时间T = O(n)

接下来初始化二维数组,若两结点没有边,则边的权值为正无穷。否则为边的文件输入的边的权所花时间T = O(n^2)

接下来为核心算法:

首先构造一维数组,一维数组值为颜色,0代表没有涂颜色。

接下来开始从第一节点开始确定其颜色,通过加一向该节点涂颜色。如果涂上某颜色后,需要判断是否与其他节点颜色冲突。 判断所花时间为线性时间**T = O(n)**

接下来在判断是否满足解空间。如果最后一个节点是部分解(有颜色且不与任何节点颜色冲突),则是解空间的一个解。此判断所花时间为线性时间T = O(1),之后直接退出双层循环即可

如果图的解空间为空,则需要两层whlie循环需要时间为O(number^color)

参考代码

#include <bits/stdc++.h>
using namespace std;
#define INF 999
bool solve(vector<int>c){
int len = c.size();
--len;
if(c[len] != 0){return true;}
return false;
}
bool judge( vector<vector<int> > v,int k,vector<int> c){

for(int i = 1 ;i < v.size() ; ++i){
if(v[k][i] != INF){
if(c[k] == c[i]){return false;}
}
}
return true;
}
int main()
{
char buffer[220];
ifstream in("Three_color.txt");
int number = 0,color= 0,sidenumber = 0 ;
in.getline(buffer,20);
sscanf(buffer,"%d%d%d",&number,&color,&sidenumber);
vector<vector<int> > v(number+1);
for(int i = 1 ; i < v.size() ; ++i){
v[i].resize(number+1);
}
for(int i = 1 ; i < v.size() ; ++i){
for(int j = 1 ; j < v[i].size(); ++j){
v[i][j] = INF;
}
}

for(int i = 1 ; i<= sidenumber ; ++i){
in.getline(buffer,20);
int m = 0 , n = 0 ,w = 0;
sscanf(buffer,"%d%d%d",&m,&n,&w);
v[m][n] = w ;
v[n][m] = w ;
}

vector<int> c(number+1);
for(int k = 1 ; k <= number ; ++k){
c[k] = 0;
}
int k = 1 ;
bool flag = false ;
while(k >= 1){
while(c[k] <= color && k <= number){
c[k] += 1 ;
if(judge(v,k,c)){
if(solve(c)){ flag = true ; break;}
k += 1 ;
}
}
if(flag){break;}
c[k] = 0 ;
k -= 1 ;
}

if(!flag){cout << "no solution !" ;}
else{
for(int i = 1 ; i < c.size() ; ++i) {cout<<c[i]<<" ";}
}
return 0;
}

谢谢访问