问题描述

关于图的m着色问题的疑问

回溯算法的Backtrack()函数里最后为什么要有x[i]=0，不然结果不是显示的所有着色方案。
#include "stdio.h"
#include "string.h"
#define MAX 10

int n; //图中的顶点数
int m; //颜色数
int a[6][6]; //邻接矩阵
int cn; //当前已着色顶点数
int sum = 0; //着色方案数
int x[MAX]; //x[i]=j表示第i个顶点用第j种颜色进行着色
int bestx[MAX];

int ok(int i) //检查当前结点所着颜色是否与前面的顶点冲突
{
int j;
for(j=1; j<=n; j++)
if((a[i][j]==1) && (x[i]==x[j])) //如果与图中顶点相邻，且着色相同
return 0; //则说明冲突
return 1;
}

//搜索到第i层，前i-1层已经着色
void backtrack(int i)
{
if(i>n) //如果搜索到叶结点
{
sum++; //着色方案数增加
int j;
for(j=1; j<=n; j++) //着色方案
bestx[j] = x[j];
}
else
{
int j;
for(j=1; j<=m; j++) //搜索m叉树，每一个结点都有m中颜色可选
{
x[i] = j; //为第i个结点着色
if(ok(i)==1) //检查当前结点所着颜色没有与前面的顶点冲突
backtrack(i+1); //为下一个顶点着色
x[i]=0;

}
}
}

void color(int a1[6][6], int n1, int m1)
{
n = n1;
m = m1;
int i, j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
a[i][j] = a1[i][j];
for(i=1; i<=n; i++)
x[i] = 0;
backtrack(1);
}

int main()
{
int n1 = 5;
int m1 = 4;
int a1[6][6]={
{0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 0},
{0, 1, 0, 1, 1, 1},
{0, 1, 1, 0, 1, 0},
{0, 1, 1, 1, 0, 1},
{0, 0, 1, 0, 1, 0},
};
color(a1, n1, m1);
printf("邻接矩阵为：
");
int i, j;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
printf("%d ", a[i][j]);
printf("
");
}
printf("着色方案数为：%d
", sum);
return 0;
}

解决方案

关于图的m着色问题
图的M着色问题
m图着色问题