回溯法求解图着色问题
程序员文章站
2022-06-09 18:37:51
...
回溯法求解图着色问题
#include <iostream>
#include <cstdlib>
using namespace std;
#define n 5
#define m 3
#define ML 1000000
int g[n][n]={{1,1,1,0,0},{1,1,1,1,1},{1,1,1,1,0},{0,1,1,1,1},{0,1,0,1,1}};
int x[n]= {0,0,0,0,0},sum=0;
bool OK(int t)
{
for(int j=0;j<t;j++)
{
if(g[t][j])
{
if(x[j]==x[t])
{
return false;
}
}
}
return true;
}
void Backtrack(int t)
{
if(t==n)//到达叶子节点
{
sum++;
cout<<"第"<<sum<<"种方案: "<<endl;
for(int i=0;i<n;i++)
{
cout<<x[i]<<" ";
}
cout<<endl;
return;
}
for(int i=1;i<=m;i++)
{
x[t]=i;
if(OK(t))
{
Backtrack(t+1);
}
}
}
int main()
{
Backtrack(0);
return 0;
}
上一篇: 基础面试题整理2