DFS 着色最少颜色

给一个图，相邻的结点关系已给出，求给图着色最少要多少种颜色。

#include <stdio.h>
#include <iostream>
using namespace std;
int t;
int count=0;
int arr[20][20];
int color[20]={0};
bool judge(int x){
for(int j=1;j<=t;j++){
if(arr[x][j]==1 && color[x]==color[j]){
return false;
}
}
return true;
}
int DFS(int index,int num){
if(index==t+1){
return 1;
}
for(int i=1;i<=num;i++){
color[index]=i;
if(judge(index)){
if(DFS(index+1,num))
return 1;
}
}
return 0;
}
void init(){
count=1;
for(int i=1;i<t;i++){
color[i]=0;
}
}
int main(){
//freopen("1.txt","r",stdin); //打开文件，测试程序，可以取消这行注释
while(cin>>t && t!=0){
init();
for(int i=1;i<=t;i++)
for(int j=1;j<=t;j++)
cin>>arr[i][j];
for(int i=1;i<=t;i++)
if(DFS(1,i)){
count=i;
break;
}
cout<<count<<endl;
}
//fclose(stdin);//关闭文件
return 0;
}

测试数据集

2
0 0
0 0
4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
5
0 1 1 1 0
1 0 1 1 1
1 1 0 1 0
1 1 1 0 1
0 1 0 1 0
0

最后

以上就是土豪绿草为你收集整理的DFS 着色最少颜色的全部内容，希望文章能够帮你解决DFS 着色最少颜色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。