首页 > 试题广场 > 已知如下递归代码用于求解图的m着色问题:#define&nb
[单选题]
已知如下递归代码用于求解图的m着色问题:
#define N 10
int a[N+1][N+1]; //存储图
int x[N+1];//记录颜色
int sum=0;//保存可着色方案数

void backtrace(int t,int m)
{
int i;
if(t>N)//搜索至叶节点
{
sum++;
printf("第%d种方案:\n",sum);
for(i=1;i<=N;i++)
printf("%d ",x[i]);
printf("\n");
}
else
{
for(i=1;i<=m;i++) //逐个判断每种颜色
{
if(check(t,i))
{   x[t]=i;
backtrace(t+1,m);
}
}
}
}
其中check()函数用于检测某个节点颜色是否合法,以下check()函数正确的是:
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1&amp;&amp;x[i]==j)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1||x[i]==j)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1||x[j]==i)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1&amp;&amp;x[j]==i)                  return 0;            }     return 1; }
这什么换行 看吐了
发表于 2019-12-05 22:03:44 回复(0)

好难啊 不会做

发表于 2019-10-27 19:58:36 回复(0)
#include<iostream>
using namespace std;

int v,e,graph[100][100];//v顶点数, e边数, graph图的邻接矩阵 
int c,color[100];//c颜色数  color当前边的颜色 
int sum = 0;//着色方法的数目 

//判断当前位置的颜色是否和相邻位置颜色重复 
bool ok(int cur){
    for(int i=1; i<=v; i++){
        if(graph[cur][i] && color[cur] == color[i]){//如果坐标(cur,i)相邻 且 cur的颜色和i的颜色相同 
            return false; 
        }
    }
    return true;
}

void backtrace(int cur){
    if(cur > v){
        sum++;
    } else {
        for(int i=1; i<=c; i++){//分别为cur位置尝试第i中颜色 
            color[cur] = i;//表示cur位置图上第i种颜色 
            if(ok(cur)){
                backtrace(cur+1);
            }
            color[cur] = 0;
        }
    }
}

int main(){
    cout << "输入顶点数和颜色数量:" ;
    cin >> v >> c;
    cout << endl;
    //输入邻接矩阵 
    for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            cin >> graph[i][j];
        }
    }
    backtrace(1);
    cout << sum;
}

发表于 2020-04-15 22:40:24 回复(0)